Select the smallest value and put it in place.

  1. Loop through the array and find the smallest value.
  2. Then swap that value with the first index which has not been swapped yet
  3. After looping through the array, the smallest value should have been selected and put in place
  4. Repeat the above steps until sorted

Efficiency notes:

  • If the smallest value is already in place then there is no need to do a "swap".
  • Pointer must never point at last value, since there are no values above it to compare with.

Let's sort an array of ints as an example: [ 5, 2, 1, 4, 3 ]

Iteration 1:

pointer = 0 smallestValuesIndex = 0

  • [ 5, 2, 1, 4, 3 ] smallestValuesIndex = 2 (val=1)
  • Swap pointer(0) and smallestValuesIndex(2) [ 1, 2, 5, 4, 3 ]

Iteration 2:

pointer = 1 smallestValuesIndex = 1

  • [ 1, 2, 5, 4, 3 ] smallestValuesIndex = 1 (val=2)
  • smallestValuesIndex already in place and dont have to swap [ 1, 2, 5, 4, 3 ]

Iteration 3:

pointer = 2 smallestValuesIndex = 2

  • [ 1, 2, 5, 4, 3 ] smallestValuesIndex = 4 (val=3)
  • Swap pointer(2) and smallestValuesIndex(4) [ 1, 2, 3, 4, 5 ]

Iteration 4:

pointer = 3 smallestValuesIndex = 3

  • [ 1, 2, 3, 4, 5 ] smallestValuesIndex = 3 (val=4)
  • smallestValuesIndex already in place and dont have to swap [ 1, 2, 3, 4, 5 ]

Big O notation: O(n2) because the outer loop runs n times & the inner loop runs (n-1)/2 times (it reduces by 1 each iteraction)

Not data sensitive: will run the same regardless of the order of the data

Low data movement: only one swap per iteration

In-place sort: the sorted items occupy the same storage as the original ones

Unstable sort: When a swap happens it may change the order of the duplicates

Check out these links for more info:

My Selection Sort Code