Thursday, August 19, 2010

For my Data Structure Students - Selection Sort

As mentioned earlier, i have started writing code and analyzing of various data structure area of computer science... Here is one such Sorting Algorithm called Selection Sort. In the first pass, it just finds the minimum number and exchanges it with the first place, in the second pass it finds out the second most minimum number and exchanges it with the second position.


Please find the source code of the Selection Sort from here.


The result of the code is as shown below. Please look at how at each outer loop pass, the small numbers occupy the places in the beginning of the sorted array...






Analysis:

For first outer loop, the inner loop goes for n-1 times, for the second outer loop, the inner loop goes for n-2 times and so on. The outer loop itself goes for n-1 times.

Hence f(n) = (n-1) + (n-2) + (n-3) + ....+ 2+1 = n*(n-1)/2

Hence O(n) = n^2

Hope you enjoy this...

1 comment:

Unknown said...

thanks a lot sir for posting these... These are very helpful....i hope to gain much more info from you..