How to implement Selection sort ?

Selection sort - Complexity O(n^2)

Algorithm

• Repeat below steps n-1 times (from back side)
• Find min in unsorted sub-array
• If found, swap with current element with min element

Java code

int i, j, minIdx, temp;

// n-1 passes (from back side)

for ( i = array.length - 1; i > 0; i - - )  {

    minIdx = 0;   // Assume first element is min
    // Locate smallest element between positions 1 and i

    for(j = 1; j <= i; j ++) {

           if( array[ j ] < array[ minIdx ] )

              minIdx= j;   
    }

    // Swap smallest found with element in position i

    temp = array[ minIdx ];

    array[ minIdx ] = array[ i ];

    array[ i ] = temp; 

}

Execution during all n-1 passes

84  69  76  86  94  91

84  69  76  86  94  91

84  91  76  86  94  69

84  91  76  86  94  69

84  91  94  86  76  69

84  91  94  86  76  69

86  91  94  84  76  69

86  91  94  84  76  69

86  91  94  84  76  69

94  91  86  84  76  69

94  91  86  84  76  69

94  91  86  84  76  69

ORANGE highlight indicates unsorted array to find min element.
BLUE highlight indicates sorted array (having items arranged)
YELLOW highlight indicates swapping items.