Selection Sort Algorithm

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