Question 5
Explain the technique of Selection Sort with an example.
Selection Sort divides the array into two parts — sorted sub-array and unsorted sub-array. In each pass, it finds the minimum element of the unsorted sub-array and swaps it with the leftmost unsorted element moving the sorted sub-array one element to the right.
For example, consider the following unsorted array:
| 9 | 5 | 2 | 3 |
Pass 1
At the start, the smallest element of the array is selected (which is 2) and swapped with the element at 0th index (which is 9):
| 2 | 5 | 9 | 3 |
At the end of the first pass, the smallest element is in its correct position. Length of sorted sub-array is 1 and unsorted sub-array is 3.
Pass 2
The smallest element of the unsorted sub-array is selected (which is 3) and swapped with the element at 1st index (which is 5):
| 2 | 3 | 9 | 5 |
At the end of the second pass, length of sorted sub-array is 2 and unsorted sub-array is 2.
Pass 3
The smallest element of the unsorted sub-array is selected (which is 5) and swapped with the element at 2nd index (which is 9):
| 2 | 3 | 5 | 9 |
With this, the third and final pass ends and the elements of the array are in sorted order.