Algorithms for Complete Beginners : Selection Sort

Part 3 : Selection Sort

Part 1 : Introduction and Data Structures
Part 2 : Bubble Sort

Once again hey,
     One algorithm down and another 1000 to go, so lets keep going. From the Bubble sort it was obvious that the sorting isnt a least efficient to a larger list, even for a list more than 100 numbers [although you wont see any difference on a good machine]. So there's another lot of sorting algorithms out there and this is just one of them.

Selection Sort

    Once you see the way Selection sort works, you'll wonder why one would use this instead of Bubble Sort although  the efficiency is roughly the same. Well i guess your thinking is correct, but there can be instances when "swapping" the two elements of the sequence is extremely CPU consuming bothersome [when it comes to pointers and stuff specially]. So instead you would go with an algorithm like this that will swap only when needed. For everyones sake let's go into the algorithm step by step.

Image from wiki article

How Selection Sort Works?

  Just like the Bubble Sort the implementation and the idea behind is extremely simple. The following method will be used:
1) Loop the no. of elements times (that's loop 10 times if there are 10 numbers in the sequence).
2) Find the minimum number in each case (That's you loop again in the whole array starting from one element after the current element and till end to search for a value smaller than the current element)
3) If there's a minimum, swap the minimum with the current, so always the minimum would go the front of the list.

ex: Sort a set of numbers {5,6,3,4,2} using Selection Sort

{5,6,3,4,2} First we start our main loop to iterate though the sequence, and we find number 5. We store the number and the index.
{5,6,3,4,2} Now we go searching in the REST OF THE NUMBERS to find a smaller value. We start from 6 as it's the immediate one after 5 (current element)
{5,6,3,4,2} 6 > 5 so the no minimum found yet, then move to next and it is 3. Yeah 3 < 5 a min. We swap now? NO. we store it as our minimum.
{5,6,3,4,2} Next we get 4, as 4 > 3, min is still 3, then we find 2 and 2 < 3 so clearly 2 is the minimum in the list (inner loop ends now). Now we swap the places of 2 and 5.
{2,6,3,4,5} Next in our main loop we continue and we find 6. Again go scanning this time starting with 3 as it is the immediate one after 6. We find 3 as the smallest from the sequence (excluding 2,6). And we swap.
{2,3,6,4,5} Likewise we go till the main loop is over and we get the sorted array.
{2,3,4,5,6} There's a little increase of the efficiency but let's go there later.

Pseudo-code

1. S : sequence of sortable items
2. N : number of items
4. for i = 0 to N-1 do
5.         min = S[i];
6.         min_index = i;
7.        
8.         for j=i+1 to N-1 do
9.                 if(S[j] < min)
10.                         min = S[j];
11.                         min_index = j;
12.                 end if
13.         end for
15.         S[min_index] = S[i];
16.         S[i] = min;    
17. end for

Explanation

First we take the sequence of numbers to a list or suitable data structure, in this case an Array (S). Then we take the number of elements as N (In most of the real problems this number will be given as some language like c++ wont allow you to directly get the size of an array)
Line 4: We start the main loop to iterate though the array
Line 5: We store the current value as the temporary minimum, because the minimum of the list, if no the current item should always be lower than this.
Line 6: We also save the index of the min for swapping's sake
Line 8: Start the inner cycle, remember we ALWAYS start the loop from 1 element above the current that is i+1 because the elements before the current is always sorted (or no element before the current if this is the first one)
Line 9 - 12: if there's a minimum we update the min and min index values
Line 15 - 16: At the end of the main loop we swap the current element with the minimum so that comes to the front. See it's just as another flavor of BBS :D

Now again the shooters part, so without just rolling down, try implementing this in your favorite language[s] :)

Implementation of Selection Sort in C++

1. #include<iostream>
3. using namespace std;
5. int main(){
6.     int S[] = {10,20,50,30,40,65};
7.     int N = sizeof(S)/sizeof(int);
8.    
9.     for(int i=0;i<N;i++){
10.             int min = S[i];
11.             int min_index = i;
12.            
13.             for(int j=i+1;j<N;j++){
14.                     if(S[j] < min){
15.                             min = S[j];
16.                             min_index = j;
17.                     }
18.             }
19.             S[min_index] = S[i];
20.             S[i] = min;
21.     }
22.    
23.     //Below code is not part of the algorithm
24.     for(int i=0;i<N;i++){
25.             cout << S[i] << " ";
26.     }
27. }

Implementation of Selection Sort in Java

1. class SelectionSort{
2.         public static void main(String args[]){
3.                 int S[] = {10,20,50,30,40,65};
4.                 int N = S.length;
5.                
6.                 for(int i=0;i<N;i++){
7.                         int min = S[i];
8.                         int min_index = i;
9.                        
10.                         for(int j=i+1;j<N-1;j++){
11.                                 if(S[j] < min){
12.                                         min = S[j];
13.                                         min_index = j;
14.                                 }
15.                         }
16.                        
17.                         S[min_index] = S[i];
18.                         S[i] = min;
19.                 }
20.                
22.                 for(int x:S){
23.                         System.out.print(x + " ");
24.                 }
25.         }
26. }

Output : 10 20 30 40 50 65

Efficiency of Selection Sort in BIG O :

    Now again as we are done with the awesome part, lets get into the but of booring[but mostly important] part of the tutorial. That is calculating the efficiency. As we take the usual assumptions about the CPU cycles ( O(1) == 1 CPU call), at a glace we could deduce those.

we have the main loop so it goes number-of-element times, taking as n
although we have the assignments (that is equaling, int i=9 like that) we dont count them as a major part of the algorithm as they are considerably smaller .
Then we have a inner loop that is reducing every time we advance the loop.
So we do a little OL math, we have a arithmetic sequence which reduces by 1 after each cycle. So we need to take the some of it.
that is : n + (n-1) + (n-2) + ....... + 1 == (n-1)/2
in other words sum of numbers 1 to n
when we put al together we get :  n(n-1)/2
Now we comes to some rules of BIG Oh
it says we can simply neglec constants like 1,10,k because they wont alter the efficiency depending on the size of the input
so we renew the math to this : n^2 + n (the /2 is gone)
Now we see that when compares to n^2, n is smaller, so we make it more cleaner as this n^2 and it becomes the time complexity of the Selection Sort (well for the worst case)

Worst Case : О(n²)
Average : О(n log n )

when we take log n it means, if
n == 4, log n = 2
n == 64, log n = 6 like that

So here comes the end of another booming chapter :D Well after this comes some harder kind of sorts and well i dont want to bore you with for ever sorting, so there will be some searching stuff as well. For now, good night ;) :D