Selection Sort Algorithm for Absolute Beginners
From the Bubble sort it was obvious that the sorting isn't efficient for 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
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.
How Selection Sort Works?
Just like the Bubble Sort the implementation and the idea behind is extremely simple. The following method will be used:
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)
Implementation of Selection Sort in C++
Implementation of Selection Sort in Java
Now again as we are done with the awesome part, lets get into the but of boring[but most 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 i.e. 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^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
Re: Selection Sort Algorithm for Absolute Beginners
Nice discussion and implementation. You are right, I think selection sort is the easiest in implement and manipulate. Scholars mostly start learning sorting technique with it.
|All times are GMT +5.5. The time now is 21:31.|