Saturday, September 5, 2009

Art of computer programming -Sorting #1

Long since Ive posted something. This time we will learn sorting. Sorting is familiar to you and to me for many years. But there are aspects of it which I haven't heard about ever since I first knew it. Those will be the points of discussion here.

Sorting by counting :
I cant say this is the best method. But every method has its advantages and disadvantages when used appropriately.

set count[i]=0 for all i from 0 to n-1
for(i=n;i>1;i++) {
for(j=i-1;j>=1;j++) {
if element[i]>element[j] count[i]++;
else count[j]++;

Now we have an auxiliary table within which we have the position of the elements in the sorted list.
Distribution counting sort:
This technique is applicable when we have to sort the numbers which belongs to a small range.
That is all the values to sort should be less than v(upper limit) and greater than u(lower limit) and v-u is small(<10 i="0;i). In such cases we can use the sorting by counting method to its full use and it'll give much better efficiency than any other method.