In the selection sort, the smallest value among the array’s unsorted items is chosen in each pass and inserted into the proper spot.
To begin, locate the array’s smallest element and set it in the first position. Moreover,Then locate the array’s second smallest element and set it in the second spot. The procedure is repeated till the sorted array is obtained.
The n-1 pass of the selection sort algorithm is used to sort the array of n entries.
The smallest element of the array, as well as its index pos, must be identified in the first run. furthermore, Swap A[0] and A[pos] after that. As a result of sorting A[0], we now have n -1 elements to sort.
The location pos of the smallest element in the sub-array A[n-1] is obtained in the second pas. In addition, Swap A[1] and A[pos] after that. After sorting A[0] and A[1], we’re left with n-2 unsorted elements.
The position pos of the smaller element between A[n-1] and A[n-2] must be found in the n-1st pass. Swap A[pos] and A[n-1] after that.
As a result, the items A[0], A[1], A[2],…., A[n-1] are sorted using the procedure described above.
Example of selection sort
For instance, Consider the following six-element array. Using selection sort, sort the array’s elements.
A = {10, 2, 3, 90, 43, 56}.
| Pass | Pos | A[0] | A[1] | A[2] | A[3] | A[4] | A[5] |
| 1 | 1 | 2 | 10 | 3 | 90 | 43 | 56 |
| 2 | 2 | 2 | 3 | 10 | 90 | 43 | 56 |
| 3 | 2 | 2 | 3 | 10 | 90 | 43 | 56 |
| 4 | 4 | 2 | 3 | 10 | 43 | 90 | 56 |
| 5 | 5 | 2 | 3 | 10 | 43 | 56 | 90 |
Sorted A = {2, 3, 10, 43, 56, 90}
Algorithm
SELECTION SORT(ARR, N)
Step1: Repeat Steps 2 and 3 for K = 1 to N-1
Step2: CALL SMALLEST(ARR, K, N, POS)
Step 3: SWAP A[K] with ARR[POS] [END OF LOOP]
Step4: EXIT
SMALLEST (ARR, K, N, POS)
Step 1: [INITIALIZE] SET SMALL = ARR[K]
Step 2: [INITIALIZE] SET POS = K
Step3: Repeat for J = K+1 to N -1
IF SMALL > ARR[J]
SET SMALL = ARR[J]
SET POS = J
[END OF IF]
[END OF LOOP]
Step 4: RETURN POS
Interested in learning about similar topics? Here are a few hand-picked blogs for you!