Please explain the procedure for Selection Sort along with the code in detail?

144 views
Please explain the procedure for Selection Sort along with the code in detail?
posted May 20, 2015

+1 vote

Let me explain this as simple as possible.

As the name suggest you have to select an element and put it in to a proper position.

So considering to sort elements from minimum to maximum elements.

1> Divide the total elements to in to two groups
Sorted Element Group and Unsorted Element group, so initially the complete array will be part of unsorted list.
2> Find minimum element each time in the unsorted group of element and add the element in the end of sorted element group, initially sorted element group will have zero elements.
3> At the end the the unsorted element will be having zero elements and your array/list will be sorted.

Considering
3 2 5 1 4

Unsorted Group : 3 2 5 1 4
Sorted Group : Nothing

1st pass : Find minimum in the unsorted list - i.e 1 , so extract 1 and mark place of 1 as Invalid and put 1 in sorted Group
Unsorted List : 3 2 5 X 4
Sorted List : 1

2nd pass : Find minimum in the unsorted list - i.e 2 , so extract 2 and mark place of 2 as Invalid and put 2 in the end of sorted group
Unsorted List : 3 X 5 X 4
Sorted List : 1 2

Similarly
3rd Pass :
Unsorted List : X X 5 X 4
Sorted List : 1 2 3

Similarly
4th Pass :
Unsorted List : X X 5 X X
Sorted List : 1 2 3 4

5th Pass :
Unsorted List : X X X X X
Sorted List : 1 2 3 4 5

This is selection sort but you can see is that i am not doing in place sort means i am not doing sorting on the go with the same array/list, instead of that i am allocating a different block of memory for storing sorted elements.

So we can make this in place sort by just swapping the minimum element variable with the actual place where it should present in the order.

So each iteration we find the minimum element from the unsorted group and swap it with the actual position element.

SP UNP
--- 3 2 5 1 4 Find minimum = 1, so swap value of 1's current position and actual position to be present
-1 2 5 3 4 Find minimum by scanning unsorted part ( 2's position to end ) Minimum = 2, so same position no sawp
similarly
1 2 3 5 4
1 2 3 4 5

Now sorted

Just for graphical representation i have slowed down the image speed present in Wikipedia which will give clear view to it, but qyeryhome does not support gif image so given direct link https://en.wikipedia.org/wiki/File:Selection-Sort-Animation.gif

If you facing problem while viewing it just use http://ezgif.com/ to slow the speed of image animation and you will understand correctly.

If you understood the explanation properly , then you can code for it perfectly by helping yourself.