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

Array	Lowest
3, 2, 5, 1, 4	2
3, 2, 5, 1, 4	2
3, 2, 5, 1, 4	1
3, 2, 5, 1, 4	1

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

Step 2

Array	Lowest
1, 2, 5, 3, 4	5
1, 2, 5, 3, 4	3
1, 2, 5, 3, 4	3

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

Step 3

Array	Lowest
1, 2, 5, 3, 4	3
1, 2, 5, 3, 4	3

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

Step 4

Array	Lowest
1, 2, 3, 5, 4	4

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;

                }

            }

        }

There are 6 comments on this article.

Azeem

2011-05-13 21:13:26

its really helpful for me.......

sahil raina

2011-10-19 12:16:09

the explanation is good.can i have the code for all sorting and searching techniques in c++.it will b g8 of you.
thank you

Anu

2011-11-14 04:19:34

I understood the concept by looking at this example, i was really confused about how it finds min element. thank you very much

uthappa c.n

2011-11-20 17:55:52

its really nice.....

amir

2012-01-29 22:04:44

more helpful for the presentation in our class thanks of almighty allah

HAIDER ALI

2012-01-30 14:17:53

very very briefly explained

Leave a message!

If you have any question or just want to leave a message, just fill out the form below!

Your e-mail will not be visible in your post, it is for validation reasons only

Name:
E-mail:
Comment: