Sorting Algorithms

[6431hoho]

I've learned bubble, insertion and selection sorts in programming class, but I'm interested in learning these algorithms also:

 

Heap sort

Merge sort

Quick sort

Selection sort

Shell sort

 

Could someone explain how these sorts work please?

Thank you.

[the tree]

Quick sort

Pick an arbitary item in your set (preferably centeral). Move all the stuff that should be to the left, to it's left and the stuff that should be to the right, to the right. This item is now in the correct place and shouldn't be moved again.

Repeat until no more movements are possible.

[Dave]

Wikipedia has an excellent article on the quicksort algorithm, with plenty of code and such to document it. The heapsort, amongst others, is well documented in the Numerical Recipies in C book.

[RyanJ]

Wikipedia has an excellent article on the quicksort algorithm, with plenty of code and such to document it. The heapsort, amongst others, is well documented in the Numerical Recipies in C[/url'] book.

 

 

Yup, I believe this is it: http://en.wikipedia.org/wiki/Sorting_algorithm

 

Covers quick sort as well as more then I have ever used... Enjoy!

 

Cheers,

 

Ryan Jones

[6431hoho]

Thank you and I read wikipedia but still couldn't grasp what was going on.

 

It says Merge Sort divides arrays in havles, sorts and merges back together.

 

But how does it (the process of sorting and merging) actually work?

[RyanJ]

Thank you and I read wikipedia but still couldn't grasp what was going on.

 

It says Merge Sort divides arrays in havles' date=' sorts and merges back together.

 

But how does it (the process of sorting and merging) actually work?[/quote']

 

Interesting this should come up. http://critticall.com/

 

A new sorting algorithm, better then quick sort.

 

It has a graphical demo on the page, you'll see how its working

 

Cheers,

 

Ryan Jones

[tomazkristan]

http://critticall.com/underconstruction.html

 

Here is the C++ source code of a new algorithm.

[necroforest]

They didn't bother to put any analysis on it other than a few examples? Is it an $O(n log n)$ algorithm or an $O(n^2)$ algorithm (like Quick Sort)?

[Dave]

I'm somewhat reticent to take their data at face value without some sort of analysis of the algorithm. But even at a quick glance, it doesn't look like a significant improvement; much less than 1% for the larger range of random numbers, which is all we really care about.

[Aeternus]

Thank you and I read wikipedia but still couldn't grasp what was going on.

 

It says Merge Sort divides arrays in havles, sorts and merges back together.

 

But how does it (the process of sorting and merging) actually work?

 

IIRC, Merge sort is similar in idea to Quick sort, you pick an element and then put some elements to the left and right and call merge sort on them.

 

The difference between the two is that in the case of quick sort, you put all the elements say less than the pivot to the left, and greater than the pivot to the right, so if you pick a bad pivot, things can become rather one sided with only a couple of values to the left and lots of values to the right. This is why quicksort's worst case is O(n^2) rather than O(nlogn) (not sure if you understand O notation, if not check wikipedia gain, it answers all).

 

In the case of merge sort, it doesn't bother to check whether something is less than or greater than a pivot, it just shoves half the values in group A, half in group B and then runs merge sort on each group. That will return in each group a sorted list of values in that group and then you can just merge these two back together into the full sorted list by just taking the smallest element from the front of each list and making that the next element. This means that there is slightly more work at each step than quicksort but overall it works out as O(nlogn).

 

However, because mergesort does that little bit of extra work merging things together and potentially create additional lists etc depending on the implementation, quicksort tends to be somewhat quicker in practice than mergesort (from what I remember) (as it's average case is O(nlogn)).

 

At least that's as far as I remember, a review of the wiki page will probably tell you more but hopefully this might help.

 

WRT Heap Sort, IIRC, it just chucks things into a Heap, a tree based structure that just guarantees that things either get bigger or small (well actually satisfies a given heap property but meh) as you go from parent to child down the tree. So if you have say a minimum-heap, the least value is at the top and values get bigger as you go down the tree. Building this tree and inserting elements is fairly trivial (just like inserting into a binary search tree with a few minor changes) and then you can take the root off as the first value of the sorted set of data, the new head is the minimum of the two (or more, I think a heap is general enough) children and you rearrange the tree fairly simply to maintain the heap property, and then you just keep repeating this, removing the root and making it the next element in the sorted result (as it is always the minimum in the heap). You might want to look this up a bit more as my explanation has probably been poor.

[bascule]

I highly recommend Knuth's The Art of Computer Programming: Vol 1: Fundamental Algorithms for this sort of thing.