This post shows how to write Selection sort program in Java.
Selection sort is also an in place sorting algorithm like Bubble sort that works by comparing and swapping elements in each pass.
Selection sort algorithm
Selection sort works as follows-
- Start with the left most element (index 0) and compare it with the elements on the right side to see if there is any element smaller than that element. If yes then this new element becomes the lowest element for further comparisons in that iteration.
- By the end of the iteration you get the index of the lowest element.
- Swap the lowest element with the leftmost element. So, by the end of the first pass you have the lowest element at its proper place.
- In the next pass start with index 1 and again follow the same process.
For example if array is {5, 4, 7, 1, 8} then start with element at index 0 and compare it with adjacent element.
After first pass you have the index of the lowest element which is then swapped with the element at index 0. That ends the first pass.
In the second pass start with the 4 (element at index 1) and again compare the elements.
Selection sort Java Program
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
System.out.println("Original array- " + Arrays.toString(arr));
int[] sortedArray = selectionSort(arr);
System.out.println("Sorted array- " + Arrays.toString(sortedArray));
}
private static int[] selectionSort(int[] arr){
int index;
for(int i = 0; i < arr.length - 1; i++){
index = i;
for(int j = i+1; j < arr.length; j++){
//if lower than the current lowest assign this index
if(arr[j] < arr[index]){
index = j;
}
}
// swap so that smallest element in this pass
// is at its proper place
swapElements(i, index, arr);
}
return arr;
}
private static void swapElements(int index, int lowest, int[] arr){
int temp = arr[index];
arr[index] = arr[lowest];
arr[lowest] = temp;
}
}
Output
Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45] Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]
Selection sort space and time complexity
Time complexity of selection sort is O(N2) which is same as the time complexity of bubble sort but the number of swaps required are comparatively lesser in Selection sort than Bubble sort.
No extra space is required so the space complexity of Selection sort is O(1).
That's all for the topic Selection Sort Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment