In this post I would be discussing selection sort. In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large arrays, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input array into two parts: the sub-array of items already sorted, which is built up from left to right at the front (left) of the array, and the sub-array of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sub-array is empty and the unsorted sub-array is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sub-array, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sub-array boundaries one element to the right.

Let us understand selection sort with the help of an example. Let’s say we want to sort 8, 5, 2, 6, 9, 3, 1, 4, 0 and 7. The finding of the minimum element of the sub-array and swapping would be as follows:

8 5 2 6 9 3 1 4 0 7   Min at index 8, swap a[ 0 ] &  a[ 8 ]
0 5 2 6 9 3 1 4 8 7   Min at index 6, swap a[ 1 ] &  a[ 6 ]
0 1 2 6 9 3 5 4 8 7   Min at index 5, swap a[ 3 ] &  a[ 5 ]
0 1 2 3 9 6 5 4 8 7   Min at index 7, swap a[ 4 ] &  a[ 7 ]
0 1 2 3 4 6 5 9 8 7   Min at index 6, swap a[ 5 ] &  a[ 6 ]
0 1 2 3 4 5 6 9 8 7   Min at index 9, swap a[ 7 ] &  a[ 9 ]
0 1 2 3 4 5 6 7 8 9

The Java program to sort an array in ascending order using selection sort is as follows:

class SelectionSort{
    public static int[] selectionSort( int a[] ){
        int temp, pos;
        for( int i = 0;  i < a.length - 1 ; i++ ){
            pos= i;
            for( int x = i + 1; x < a.length ; x++ ){
                if( a[ x ] < a[ pos ] ){
                    pos = x;
                }
            }
            if( pos != i ){
                temp = a[ i ];
                a[ i ] = a[ pos ];
                a[ pos ] = temp;
            }
        }
        return a;
    }
    public static void display( int a[] ){
        for( int n: a ){
            System.out.print( n + " " );
        }
        System.out.println();
    }
    public static void main( String args[] ){
        int a[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 };
        a = selectionSort( a );
        display( a );
    }
}

In the above program, the outer loop on line number 6 is for managing the left sorted sub-array and the inner loop on line number 6 is for managing the right unsorted sub-array. The only change required in the above program to change the sort order from ascending to descending would be to change the < to > where we are comparing the two elements for finding the minimum (line number 6). As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.