Selection Sort Programming Code Explained
21 April 5:53pm – 5 August 6:13 am 2020
--------------------------------------
Selection Sort is a sorting algorithm where we assume/select that the first element is the smallest element(considering ascending order). Then we compare it with the next one i.e., the second one. If this selected(first) element is smaller, we compare it with the next one i.e., the third one. We keep comparing it with the next ones (i.e., the fourth one, fifth one and so on) as long as it is smaller. Our main goal is to find the actual smallest element.
Let’s assume, at one stage, we find the fourth element is smaller than the first element(our assumed smallest element). So now we will assume/select the fourth element is the smallest element. Now that this fourth one is our assumed/selected smallest item, it will be compared with the fifth one, and then the sixth one and so on as long as it is smaller.
The main concept is that at first we assume the zero indexed item is the smallest item and keep comparing it with the next items as long as it is smaller. Whenever we find any item smaller than it, then we select that item smallest and keep comparing it with the next items as long as it is smaller.
The process will go on till the last item. After the first iteration we must find the actual smallest item, and it will be swaped with the zero indexed item.
Now the zero indexed item is the actual smallest item. The second iteration will start from the one indexed item as the zero indexed item has already been sorted. The process will go on like I described above. After the second iteration we will find the second smallest item, and naturally it will be swaped with the one indexed item. Now we have two sorted elements - zero index and one index.
The third iteration will start from two indexed item as zero and one is sorted already. In this way we will ultimately find a sorted array.
Let’s consider an unsorted array which we are going to sort using Selection Sort algorithm. See the picture below.
Here is an unsorted array which has 5 elements. We’re going to use two nested loops- i-loop and j-loop. The i-loop is outer and the j is inner.
The j-loop will make the comparison.
In the first i-loop iteration, we will select the zero indexed item as the smallest item. Then the j-loop will compare this item with the other items. So the i-loop will start from 0 and j-loop from 1 index. And i-loop will end at the element just before the last(n-2). The j-loop will end at the last element(n-1). In the last iteration of the i-loop, the third element (n-2) will just need to be compared with the last element(n-1). That’s why the i-loop ends at the 3 indexed element and the j-loop ends at the 4 indexed element i.e. the last element of the array. I think now it’s clear why the i-loop will continue from 0 to n-2 and the j-loop from 1 to n-1.
After the first iteration of the i-loop(and naturally all iterations of the j-loop) it will give us the smallest item and swap it(the smallest item) with the 0 indexed item. So we have our first sorted item at 0 index position.
Then the i-loop will initiate it’s second iteration from 1 index and the j-loop from 2 index. The j-loop will compare the 1 index item with the other items. At the end of all iterations of the j-loop, it will find the smallest item. And at the end of the i-loop iteration i.e., the second iteration, it will put the smallest item at the 1 index position. So now we have two sorted items at 0 index and 1 index. The process will continue till it reaches the last item.
If you’re still confused, see the demostration below and the above code simultaneously.
------------------
i = 0 => index_min = i = 0
j = 1 => if A[j] < A[index_min]
A[1] < A[0]
5 < 8 true
index_min = j = 1
j = 2 => if A[j] < A[index_min]
A[2] < A[1]
9 < 5 false
j = 3 => if A[j] < A[index_min]
A[3] < A[1]
3 < 5 true
index_min = j = 3
j = 4 => if A[j] < A[index_min]
A[4] < A[3]
1 < 3 true
index_min = j = 4
if index_min != i
ð 4 != 0 true
A[i] and A[index_min] will interchange their positions
A[0], A[4]
8, 1
1, 8
Now the element positions will be: 1 5 9 3 8 [previous positions 8 5 9 3 1]
----------------------------------------------------------------
i = 1 => index_min = i = 1
j = 2 => if A[j] < A[index_min]
A[2] < A[1]
9 < 5 false
j = 3 => if A[j] < A[index_min]
A[3] < A[1]
3 < 5 true
index_min = j = 3
j = 4 => if A[j] < A[index_min]
A[4] < A[3]
8 < 3 false
if index_min != i
ð 3 != 1 true
A[i] and A[index_min] will interchange their positions
A[1], A[3]
5, 3
3, 5
Now the element positions will be: 1 3 9 5 8 [previous positions 1 5 9 3 8]
----------------------------------------------------------
i = 2 => index_min = i = 2
j = 3 => if A[j] < A[index_min]
A[3] < A[2]
5 < 9 true
index_min = j = 3
j = 4 => if A[j] < A[index_min]
A[4] < A[3]
8 < 5 false
if index_min != i
ð 3 != 2 true
A[i] and A[index_min] will interchange their positions
A[2], A[3]
9, 5
5, 9
Now the element positions will be: 1 3 5 9 8 [previous positions 1 3 9 5 8]
--------------------------------------------------------------------
i = 3 => index_min = i = 3
j = 4 => if A[j] < A[index_min]
A[4] < A[3]
8 < 9 true
index_min = j = 4
if index_min != i
ð 4 != 3 true
A[i] and A[index_min] will interchange their positions
A[3], A[4]
9, 8
8, 9
Now the element positions will be: 1 3 5 8 9 [previous positions 1 3 5 9 8]
------------------------------------------------------------------
And now our array elements have already been sorted: 1 3 5 8 9
------------------------------
I strongly believe that now you have a clear idea about Selection Sort algorithm.
Comments
Post a Comment