PDA

View Full Version : Sorting Algorithms



dinesh
11-15-2003, 12:47 AM
We use several sorting algorithms these days. What are the best ones, performance wise, in your opinion?
Please give results in best/average/worst cases?

It will also help if you can explain how the algorithm works....

silican
11-15-2003, 12:59 AM
Im not a Programmer basically. So I havent used much of Sorting Algorithms other than Bubble-sort. I know its very slow when u go for large arrays. But I prefer ths one as most of my computations involve smaller arrays and moreover its easy.

anainar
11-15-2003, 01:18 AM
Dinesh,

I used to write programs and did this as excercise during masters. But dont have the results. After I started professional code writing in 1995, never had to write code for sorting/searching and such kind of rudimentary tasks. I have used a bunch of libraries Roguewave product which provide all these functionalities.

Sorting generally has two overheads. One is number of comparisons and the other is number of exchanges. There is a third one which is not relevant now, which is storage space, with memory becoming so cheap, that no longer is a criteria production software guy look at in the first place. As a general rule for non ordered N element array, sorting by bubble sort, selection sort, insertion sort all require factors of N*N comparisons and factors of N*N exchanges. The only other algorithm that is much faster is Quicksort, which normally is in the range of NlogN operations. That is provided as a standard C library function in most of the UNIX boxes. I am not sure about Windows whether MFC has built in functions.

So, if you are in UNIX, dont pain yourself writing sorting code. Use qsort which is readily available to you.

Cheers.

mpalanieppan
11-15-2003, 05:21 AM
The newer sorting methods that attempt to reduce the time complexity raised by swapping that i know of is shell sort. Instead of bubble sort, which compares and swaps each adjacent elements if required, shell sort attempts to compare and swap elements that are of certain distances away, and progress towards comparing adjacent elements, the idea being, by swapping distant elements, we are actually reducing the number of swaps than that would have occured in O(n^2) algorithm (i.e. when we come to stage of comparing adjacent elements, lot of them are already sorted and we just do comparisons. It has been shown mathematically that the time complexity of the algorithm can go as low as O(n^(4/3)), depending on how we choose the distances of comparisons...(e.g 1,8,23,77...called Sedgewick sequence, named after the inventor)An example would be given an array of length say, 80, we start by comparing the current element of an array with the element 77 positions away, then 23, then 8, etc. The running time will dramatically be reduced in case large arrays, say millions of elements.

M.Palanieppan

mpalanieppan
11-15-2003, 05:27 AM
The other n log n sorting algorithms are merge sort and heap sort, the former involving breaking up the arrays into smaller unit and sort them and then combine back, and the latter involving putting the elements of array into binary heap. The best running time i heard of so far is the sedgewick shell sort (mentioned above) which runs in O(n^(4/3)). I have not really thought about space complexity, but as anainar says, the emphasis is not much on space as on time complexity of an algorithm.

M.Palanieppan

dinesh
11-15-2003, 11:42 AM
Yes....bubble sort is quite primitive and quite costly when it comes to large datasets.
Quicksort is one of the best when it comes to the average case, and quite easy to implement too. I know that it is available in UNIX, but I was just asking people to share their experiences.
As Palaniappen said, merge/heap sort are quite effective in the worst case scenario. I've never heard about shell sort though, I will have to have a read about it. Thanks for your information, silican, nainar and palani.
:b:

kaylir
12-01-2003, 04:36 AM
sedgwick sort 's O(n^(4/3)) is higher then nlogn, since n^(1/3) is more than logn.
Probably it performs faster in practice because of the constant factor in its timecomplexity.

if the items you want to sort are records, with key-value and other associated data, then it
is better to exchange pointer to the records, instead of the records themselves. (This is what qsort does- it exchanges the records themselves - it is slightly inefficient). But qsort has been implemented very efficiently. heap-sort and merge-sort always takee nlogn whether or not the items are already partially sorted. quicksort runs fast in that case. bubblesort is the very fast if the number of items are very small like 10 or 20.

haven't heard of sedgwick sort - the sedgwick is really interesting.

Nachiappan

shalu
12-02-2003, 06:09 AM
Hi Shidinesh,
Here is a good link for knowing more about the sorting algorithm and the way the work. http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html Hope this helps you in some way