W2203 Selection Sort
Algorithm[edit]
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[edit]
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[edit]
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. This array would run a total of 36 times.
Similar to Bubble Sort, Selection Sort would not be a suitable choice to process large amounts of data due to its long run time. Selection Sort can be good at checking if arrays are already sorted. It can also be used if memory is limited since Selection Sort does not wait to swap elements .
Example[edit]
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
Quiz[edit]
References[edit]
Selection Sort (Wikipedia)
Selection Sort (Khan Academy)
