Selection Sort

The following shows the state of an array after each exchange in a selection sort (where small elements are swapped towards the front of the list).


public class SelectionSorter {
    
    ///////// "helper" methods //////////
    
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void printOrder(Comparable[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(b[i] + "  ");
        }
        System.out.println();
    }
    
    public static void printIndices(Comparable[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (int i = 0; i < b.length; i++) {
            System.out.print("---");
        }
        System.out.println();
    }

    ///////////////////////////////////////
    
    public static void selectionSort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int minPos = i;
            for (int j = i+1; j < n; j++) {
                if (less(a[j],a[minPos])) {
                    minPos = j;
                }
            }
            exch(a,i,minPos);
            printOrder(a);
        }
    }
    
    public static void main(String[] args) {
        Character[] a = {'K','R','A','T','E','L','E','P','U','I'};
        
        System.out.println("Order before selection sort application:");
        printOrder(a);
        System.out.println();
        
        printIndices(a);
        selectionSort(a);
        System.out.println();
        System.out.println("Order after selection sort application:");
        printOrder(a);
    }
}

Output

The output produced by the code above provides a trace of the selection sort, showing the state of the array after each exchange.

Order before selection sort application:
K  R  A  T  E  L  E  P  U  I  

0  1  2  3  4  5  6  7  8  9
----------------------------
A  R  K  T  E  L  E  P  U  I  
A  E  K  T  R  L  E  P  U  I  
A  E  E  T  R  L  K  P  U  I  
A  E  E  I  R  L  K  P  U  T  
A  E  E  I  K  L  R  P  U  T  
A  E  E  I  K  L  R  P  U  T  
A  E  E  I  K  L  P  R  U  T  
A  E  E  I  K  L  P  R  U  T  
A  E  E  I  K  L  P  R  T  U  
A  E  E  I  K  L  P  R  T  U  

Order after selection sort application:
A  E  E  I  K  L  P  R  T  U