Complete Computer Knowledge Portal

Wednesday, June 19, 2013

Selection Sort

It is the sorting technique with O (n2) Complexity. Hence this technique can’t be used for sorting large lists. This sorting technique finds maximum Value from the list and swaps it with first element. This process is repeated for the remaining list until list is not sorted.

Only n swaps are required to swap n number of elements.

Example: Consider the following unordered list   

10
40
7
3
25
33
                                                               

First Pass: Highest element in the list is 40 swap it with first element

40
10
7
3
25
33

40 is now first element of sorted list now we will sort remaining list considering 10 as first element

Second Pass: Now highest element is unsorted list is 33 replace it with first element i.e. 10. 

40
33
7
3
25
10

Now 40, 33 are sorted, we will now sort remaining list considering 7 as first element.

Third Pass: Now highest element is 25 replace it will first element i.e. 7

40
33
25
3
7
10

Now 40, 33, 25 are sorted, sort the remaining unsorted list considering 3 as first element

Fourth Pass: Highest element in unsorted list is now 10; replace it with first element i.e.3

40
33
25
10
7
3

Now 40, 33, 25, 10 are sorted, sort the remaining unsorted list considering 7 as first element.

Fifth Pass: Now highest element in unsorted list in 7 which is already in first position hence no swapping required.

40
33
25
10
7
3

Now 40, 33, 25, 10, 7 are sorted and we will sort remaining list considering 3 as first element.

Sixth Pass: Now highest and last element is 3 and is already at first position in unsorted list and requires no swapping.

40
33
25
10
7
3


From the above given example it is clear that for sorting 6 elements list 6 passes are required. It is also clear that after fourth our list was sorted but still we have to repeat the entire steps to generate sorted list.
Another major thing that is clear from this sorting technique is that this algorithm is very useful if we want to generate sorted list in descending order.

No comments:

Post a Comment