Difference between revisions of "W2203 Selection Sort"
Kartik-dabas (talk | contribs) (Created page with "== 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 elem...") |
|||
Line 15: | Line 15: | ||
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. | 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. | ||
Selection Sort | Similar to Bubble Sort, Selection Sort would not be a suitable choice to process large amounts of data due to low efficiency and the long run time. | ||
<br> | <br> |
Revision as of 21:23, 29 April 2021
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.
Similar to Bubble Sort, Selection Sort would not be a suitable choice to process large amounts of data due to low efficiency and the long run time.
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
References[edit]
Selection Sort (Wikipedia) Insertion Sort (Khan Academy)