MorkaLork Development

Interesting stuff I've picked up over the years...

Selection Sort

2009-09-16 15:55:32 | 611 views | C# selectionsort selection sort inner outer swap

Prologue


The selection sort algorithm may look similar to the bubble sort algorithm but actually works quite differently. Instead of checking the closest element to the right, this algorithm search the range of values for the lowest ranking element and swaps it with the currently first element in the range, it then does the same thing with the next element in the list until it has looked through the entire list.


An example:


If we are going to sort the following range of numbers:
3, 2, 5, 1, 4

We will start by comparing 3 to every number in the range, and swap it for the lowest one. In this, the first loop, we will swap 3 with 1, which is currently the lowest number in the range. The numbers will now look like this:
1, 2, 5, 3, 4

We then continue by checking 2, the second element, with the rest of the elements. There is, however, no value after 2 that is lower than it, so it will have to stay put. The range still looks like this:
1, 2, 5, 3, 4

So we check the third element in the range, 5. It turns out that 3 is the lowest value within the range of numbers left, so we swap 5 and 3. The numbers will now look like this:
1, 2, 3, 5, 4

And so we make a fourth check, and as 4 is the lowest number, and is lower than 5, we swap them and end up with this:
1, 2, 3, 4, 5

We can make no more checks since there are no numbers left, but as we can see, the range of numbers is now perfectly sorted, and we have sorted it in very logical manners.


A visual of how it works


The array:
3, 2, 5, 1, 4

Step 1


ArrayLowest
3, 2, 5, 1, 42
3, 2, 5, 1, 42
3, 2, 5, 1, 41
3, 2, 5, 1, 41

Lowest number: 1
1 is lower than 3
Swap 3 and 1

Step 2


ArrayLowest
1, 2, 5, 3, 45
1, 2, 5, 3, 43
1, 2, 5, 3, 43

Lowest number: 3
3 is NOT lower than 2
Don’t swap

Step 3


ArrayLowest
1, 2, 5, 3, 43
1, 2, 5, 3, 43

Lowest number: 3
3 is lower than 5
Swap 5 and 3

Step 4


ArrayLowest
1, 2, 3, 5, 44

Lowest number: 4
4 is lower than 5
Swap 5 and 4


The array:
1, 2, 3, 4, 5

The sorting is now done, and it is very easy to understand, just select the lowest element, check if it’s lower than the current element used to check with, if it is, then swap them.

The Pseudo code:



Void SelectionSort(Array arr){
For (var outer = 0; outer < n; outer++){
minimum value = outer;
For(var inner = outer + 1; inner < n + 1; inner++){
If(inner value < minimum value)
minValue = inner;
}

If(outer value is not minimum value){
var temp = outer value;
outer value = minimum value;
minimum value = temp;
}
}
}


To explain the pseudo code:
We have two loops, one outer and one inner. The outerloop handles the value to check and the inner loop handles the checking with each number left to check with:
3, 2, 5, 1, 4
3, 2, 5, 1, 4
3, 2, 5, 1, 4
3, 2, 5, 1, 4
The bold number represents the outer loop while the underlined number represents the inner loop. If you look again at the “A visual of how it works” part you can see that the outer loop only moves once per step, and the inner loop moves as many steps as there are elements left to the right in the range of numbers. In the case above outer is 0 and inner loops from 1 to 4.


The C# code:




public void SelectionSort(int[] arr) {
//Outer loop
for (int outer = 0; outer < (arr.Length - 1); outer++) {
//Holds the current minimum value in the array
int min = outer;
//Inner loop
for (int inner = outer + 1; inner < arr.Length; inner++) {
//If the current value to check is lower than
//the current minimum value, set minimum value
//to the index this value
if (arr[inner] < arr[min])
min = inner;
}

//Swap
if (outer != min) {
int temp = arr[outer];
arr[outer] = arr[min];
arr[min] = temp;
}
}
}



Article comments

Feel free to comment this article using a facebook profile.

I'm using facebook accounts for identification since even akismet couldn't handle all the spam I receive every day.