**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__

- S : sequence of sortable items
- N : number of items
- for i = 0 to N-1 do
- min = S[i];
- min_index = i;
- for j=i+1 to N-1 do
- if(S[j] < min)
- min = S[j];
- min_index = j;
- end if
- end for
- S[min_index] = S[i];
- S[i] = min;
- 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++__

__Implementation of Selection Sort in Java__

*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

**and it becomes the time complexity of the Selection Sort (well for the worst case)**

*n^2*Worst Case :

*О*(

*n*

^{2})

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

## No comments:

## Post a Comment