Selection Sort Algorithm

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

Back


How To Start A Blog   HTML5   JavaScript   Sorting Algorithm