Selection Sort is a simple and slow sorting algorithm that repeatedly selects the lowest or highest element from the un-sorted section and moves it to the end of the sorted section. Mostly, performance wise, it is slower than even Insertion Sort. It does not adapt to the data in any way so its runtime is always quadratic.
But you should not conclude that selection sort should never be used. Good thing is that selection sort has the property of minimizing the number of swaps with each iteration. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.
Selection Sort Algorithm
Below is logical code structure or pseudo code of selection sort
in general.
for i = 1:n, k = i for j = i+1:n, if a[j] < a[k], k = j //-> invariant: a[k] smallest of a[i..n] swap a[i,k] //-> invariant: a[1..i] in final position end
In plain English, following things happen:
- Data elements are grouped into two sections: a sorted section (initially empty) and an un-sorted section (initially complete array).
- Assuming the sorting order is from low to high, find the element with the lowest comparable order from the un-sorted section.
- Place the found element to the end of the sorted section.
- Repeat step 2 and 3 until no more elements left in the un-sorted section.
Selection Sort Java Sourcecode
Below is a sample selection sort implementation in java.
public class SelectionSortExample { public static void main(String[] args) { // This is unsorted array Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 }; // Let's sort using selection sort selectionSort(array, 0, array.length); // Verify sorted array System.out.println(Arrays.toString(array)); } @SuppressWarnings({ "rawtypes", "unchecked" }) public static void selectionSort(Object[] array, int fromIndex, int toIndex) { Object d; for (int currentIndex = fromIndex; currentIndex < toIndex; currentIndex++) { int indexToMove = currentIndex; for (int tempIndexInLoop = currentIndex + 1; tempIndexInLoop < toIndex; tempIndexInLoop++) { if (((Comparable) array[indexToMove]).compareTo(array[tempIndexInLoop]) > 0) { //Swapping indexToMove = tempIndexInLoop; } } d = array[currentIndex]; array[currentIndex] = array[indexToMove]; array[indexToMove] = d; } } } Output: [3, 6, 10, 12, 13, 24, 70, 90]
If you guys know any way to improve the performance of selection sort, then please share. I am clueless.
Happy Learning !!
can you give examples when swapping is expensive?
If we’re sorting an array of pretty large objects, swapping takes a lot of time.