W2203 Selection Sort

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Algorithm

Selection Sort starts off by selecting the first element in the array, comparing that element with other remaining elements in the array, and if a smaller element is found, both elements are swapped, bringing the smallest element at index 0. This same process is repeated with the element in the following indices.

• Iterate over the array
• Find the smallest element in the array, assigning that element to "i".
• Swap "i" with the first index in the array, assigning that index to "j".
• Find the next smallest element in the array, assigning that element to "i".
• Swap "i" with the "j + 1" index in the array, adding one to "j".
• Repeat until the array is sorted.

Swap

You can use the same swap function as in bubble sort and selection sort because you only need to be able to swap two elements at a time.

Performance Considerations

Given an array with 8 elements, this algorithm would have to run 8 times on the first swap, 7 times on the second swap, since that is how many unsorted elements are remaining, 6 times on the third swap, and so on, until the array is sorted.

Similar to Bubble Sort, Selection Sort would not be a suitable choice to process large amounts of data due to its long run time.

Example

Here is an example with an array of 5 elements:

Array: [20, 12, 10, 5, 2] | Initial

  // The algorithm first finds the smallest element: 2. Since 2 < 20, both would be swapped, bringing 2 to the first index.

Array: [2, 12, 10, 5, 20] | Total loops ran before 1st swap: 5 
          |
  // The algorithm finds the next smallest element: 5. Since 5 < 12, both would be swapped, bringing 5 to the second index.

Array: [2, 5, 10, 12, 20] | Total loops ran before 2nd swap: 9
             |
  // The algorithm finds the next smallest element: 10. Since 10 !< 10, no swap would occur.
  
Array: [2, 5, 10, 12, 20] | Total loops ran before 3rd swap: 12
                 |
  // The algorithm finds the next smallest element: 12. Since 12 !< 12, no swap would occur.

Array: [2, 5, 10, 12, 20] | Total loops ran before 4rd swap: 14
                     |
  // The algorithm finds the next smallest element: 20. Since 20 !< 20, no swap would occur.
  // The array is now fully sorted

References

Selection Sort (Wikipedia) Insertion Sort (Khan Academy)