Selection Sort in java
The idea behind selection sort is we put the smallest item at the start of the list, then the next smallest item at the second position in the list, and so on until the list is in order.
Algorithm:
|
1 2 3 4 5 6 7 8 9 10 11 |
for i=0 to N-2 { set smallest = i for j=i+1 to N-1 { compare list[smallest] to list[j] if list[smallest] > list[j] smallest = j } swap list[i] and list[smallest] } |
Example:
72 69 27 92 7 52 65 37 69 28
We indicate the initial sub-array with square brackets and the smallest element outside the array with round brackets:
72 69 27 92 (7) 52 65 37 69 28 — find smallest
7 69 27 92 (72) 52 65 37 69 28 — swap with first outside
7 69 (27) 92 72 52 65 37 69 28 — find
7 27 (69) 92 72 52 65 37 69 28 — swap
[7 27 ] 69 92 72 52 65 37 69 (28) — find
[7 27 ] 28 92 72 52 65 37 69 (69) — swap
[7 27 28 ] 92 72 52 65 (37) 69 69 — find
[7 27 28 ] 37 72 52 65 (92) 69 69 — swap
[7 27 28 37 ] 72 (52) 65 92 69 69 — find
[7 27 28 37 ] 52 (72) 65 92 69 69 — swap
[7 27 28 37 52 ] 72 (65) 92 69 69 — find
[7 27 28 37 52 ] 65 (72) 92 69 69 — swap
[7 27 28 37 52 65 ] 72 92 (69) 69 — find
[7 27 28 37 52 65 ] 69 92 (72) 69 — swap 4
[7 27 28 37 52 65 69 ] 92 72 (69) — find
[7 27 28 37 52 65 69 ] 69 72 (92) — swap
[7 27 28 37 52 65 69 69 ] (72) 92 — find
[7 27 28 37 52 65 69 69 ] (72) 92 — swap
[7 27 28 37 52 65 69 69 72 ] (92) — find
[7 27 28 37 52 65 69 69 72 ] (92) — swap
[7 27 28 37 52 65 69 69 72 92] — Done.
Java implementation of selection sort:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public void selectionSort(int[] list) { int minIndex; // index of current minimum item in array boolean newMinFound = false; // indicates if we need to swap // items or not on this pass for (int i=0; i < list.length-1; i++) { minIndex = i; for (int j=i+1; j < list.length; j++) { if (list[j] < list[i]) { // new minimum found, update minIndex minIndex = j; newMinFound = true; } } if (newMinFound) { swap(list,i,minIndex); } newMinFound = false; // reset our ‘‘swap’’ flag } } |
The swap method looks like this
|
1 2 3 4 5 6 7 8 9 10 11 |
public void swap(int[] list, int index1, int index2) { // Save a copy of the number at the first index, so that // we don’t overwrite it int temp = list[index1]; // Copy number at second index into first index slot list[index1] = list[index2]; // Copy number that was originally in the first index slot // into the second index slot. list[index2] = temp; } |
Notice that we don’t return the array after we swap the two items. This is one feature of arrays, and of objects in general: because we refer to an array by its address, if we change an item in the array within a method, the change holds outside of the method
Performance of selection sort:
- The best case for selection sort occurs when the list is already sorted. In this case, the number of swaps is zero. We still have to compare each item in the list to each other item in the list on each pass through the 6 algorithm. The first time through, we compare the first item in the list to all other items in the list, so the number of comparisons is (N-1). The second time through, we compare the second item in the list to the remaining items in the list, so the number of comparisons is (N-2). It turns out that the total number of comparisons for selection sort in the best case is (N − 1) + (N − 2) + … + 2 + 1. This equation simplifies to N(N + 1)/2 − 1, which is approximately N2 . Thus, even in the best case, selection sort requires O(N2 ) comparisons.
- The worst case for selection sort occurs when the first item in the list is the largest, and the rest of the list is in order. In this case, we perform one swap on each pass through the algorithm, so the number of swaps is N. The number of comparisons is the same as in the best case, O(N2 ).
- The average case requires the same number of comparisons, O(N2 ), and roughly N/2 swaps. Thus, the number of swaps in the average case is O(N).
Let’s see whether selection sort is stable and in-place or not:
Stability:
Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.
Selection sort algorithm is not stable because:
Selection sort algorithm picks the minimum and swaps it with the element at current position.
Suppose the array is:5 2 3 8 4 5 6
Let’s distinguish the two 5’s as 5(a) and 5(b) .
So our array is:
5(a) 3 4 5(b) 2 6 8
After iteration 1:
2 will be swapped with the element in 1st position:
So our array becomes:
2 3 4 5(b) 5(a) 6 8
Since now our array is in sorted order and we clearly see that 5(a) comes before 5(b) in initial array but not in the sorted array.
So we can clearly see that selection sort is not stable.
In place:
In place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space.
For in-place implementation in Java, starting from 1st index, find the smallest element (takes O(n) ) and put it at the first index of unsorted sub array. So there will be 2 parts of main array, left one will have sorted element and right one will have unsorted. We choose smallest from the right one and will put it at the beginning of the unsorted sub array. Now Sorted array will have one more element and unsorted array will have one less. Continue this process till we reach the end of element. ( takes O(n)). So finding smallest for one loop will take O(n) and there will be at most n loop so it total time in worst case will be O(n^2).
Leave a Reply