In Selection sort method in each pass we locate smallest number and swap with the last element of sorted list. The selection sort method require (n-1) pass to sort an array.
Following are the steps that will more clear the concept of Selection Sort.
Pass 1: Find the location ‘loc’ of smallest element in entire array a i.e. a[0] , a[1]
,a[2],……a[n-1].
Swap a[0] and a[loc]. Then a[0] is sorted.
Pass 2: Find the location ‘loc’ of smallest element in sub array a i.e. a[1] , a[2] ,
a[3],……a[n-1].
Swap a[1] and a[loc]. Then a[0] and a[1] is sorted.
.
.
Pass k: Find the location ‘loc’ of smallest element in sub array a i.e. a[k+1] , a[k+2] ,
a[k+3],……a[n-1].
Swap a[k] and a[loc]. Then a[0] , a[1] , a[2],…….,a[k] is sorted.
Pass n-1: Find the location ‘loc’ of smallest elements a[n-2] , a[n-1] .
Swap a[n-2] and a[loc]. Then a[0] , a[1] , a[2],…….,a[n-1] is sorted.
Example
To understand the working of selection sort method, consider the following array a with 7 elements
Pass 1:
loc=location of smallest element a[4] =4
Interchange elements a[0] and a[4] i.e. 22 and 4 to obtain following array.
Pass 2:
Now the location of smallest element from a[1] to a[6] is 5.
Therefor loc = 5
Interchange elements a[1] and a[5] i.e. 36 and 12 to obtain following array.
Pass 3:
Now the location of smallest element from a[2] to a[6] is 6.
Therefor loc = 6
Interchange elements a[2] and a[6] i.e. 41 and 15 to obtain following array.
Pass 4:
Now the location of smallest element from a[3] to a[6] is 4.
Therefor loc = 4
Interchange elements a[3] and a[4] i.e. 95 and 22 to obtain following array.
Pass 5:
Now the location of smallest element from a[4] to a[6] is 5.
Therefor loc = 5
Interchange elements a[4] and a[5] i.e. 95 and 36 to obtain following array.
Pass 6:
Now the location of smallest element from a[5] and a[6] is 6.
Therefor loc = 6
Interchange elements a[5] and a[6] i.e. 95 and 41 to obtain following sorted array.
Complexity
