Selection Sort - Algorithm (Simple sorting Techniques)

Hi, This is the second part of Simple sorting techniques. I described Bubble sort   in previous post. So this post describes the Selection Sort.
consider the following unsorted array.

figure 01: unsorted array 

Round 01:(Consider all five elements)

Step 01: Mark the 0th element as minimum of the array. Then compare the current minimum with other elements. If one of the other elements is smaller than current minimum, that element become the current minimum.

figure 02: current minimum is element 0

Compare current minimum with element 1. Element 1 is smaller than current minimum. So element 1 become the current minimum. 

figure 03: current minimum is element 1

Then compare the current minimum with element 2, element 3 and element 4. But all of those elements are larger than element 2. Therefore at the end of Round 01, current minimum is element 1. 

Then current minimum should go to 0th position. And the element in 0th position come to the current minimum's position. So the current minimum and element 0 is swapped.

figure 04:current minimum go to 0th position 

At the end of Round 01, the 0th element is sorted. So it will not consider again. 

Round 02:(Consider four elements)

Step 01: Mark element 1 as current minimum (figure 05). 

figure 05

Step 02:  Compare current minimum with element 2. element 2 is smaller than current minimum. So element 2 marked as current minimum (figure 06).

figure 06

Step 03: Compare current minimum with element 3 and element 4. element 4 is smaller than current minimum. element 4 marked as current minimum (figure 07).

figure 07

At the end of Round 02, current minimum is element 4. It means element 4 is the minimum of next four elements of the array (element 1, element 2, element 3, element 4).

So the current element should come to position 1. So element 1 and element 4 swapped. 

figure 08: current minimum goes to position 1

At the end of Round 02, the first two elements are sorted. So first two elements will not consider again. 

Round 03: (Consider three elements)

Step 01: Mark element 2 as the current minimum (figure 09).

figure 09

Step 02: Compare current minimum with element 3. element 3 is larger than current minimum. so element 2 remain as current minimum. Then compare current minimum with element 4. element 4 is larger than current minimum. So the minimum of next three elements(element 2, element 3, element 4) is in the right position. No need to swap. 

At the end of Round 03, first three elements of the array are sorted. So the first three elements will not consider again. 

Round 04:(last two elements considered)

Step 01: Mark element 3 as the current minimum (figure 10).

figure 10

Step 02: Compare current minimum with element 4. element 4 is smaller than current minimum. so element 4 become current minimum(figure 11).

figure 11

It means the minimum of last two elements of the array is element 4. so the current minimum should come to position 3. So element 3 and element 4 are swapped (figure 12).

figure 12

At the end of four Rounds, the array is sorted :)

Java code for Selection Sort

In selectionSort() method, the outer loop:

for (out = 0; out < nElemns-1; out++) reoresents the Rounds. For our example number of rounds are four. In each round out is increased by one.

min=out indicates the opening current minimum for the loop is out 'th element.

The inner loop :

for (in = out+1; in < nElemns ; in++) represents the steps. As our example in the first round, out is 0. It means inner loop runs from 1(out +1) to 4(<nElemns).

While inner loop runs 1 to 4, if (values[in] < values[min])  min = in; runs for four comparisons. 

while this four comparisons running , if the condition satisfies in=n,  element n become current minimum. 

 The Runner class

Download the code from  Here