Re: Detailed explanation of how a QuickSort Works

"Paul MH" <paulmorrishill@xxxxxxxxxxxxxx> wrote in message news:1175965024.656339.275930@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Can someone who understands quicksorts please post a
detailed explanation of how they work e.g. step by step
because ive seen alot of examples and diagrams etc and i
still dont understand. i need to learn this for a program i am
writing because i dont like using code that i dont understand.

Why not? I use code that I don't understand all the time! Actually, that's only "half a joke", and the point I'm making is that lots of people, even lots of "time served professional programmers" sometimes use code that they don't understand. It isn't possible for any one person to know everything ;-)

Anyway, back to the point as they say, here is a very brief and entirely non technical explanation of how a QuickSort algorithm works.

Firstly, if you consider the simple "Bubble Sort" algorithm, it works by running through the entire data set, one item at a time, comparing each item to the previous item and swapping them if they are not already in the correct order. At the end of the first "run" the items will still not be correctly ordered, but they will be in a "better order than they were before". So, to get them into an even better order, the Buble Sort algorithm needs to run through the entire list again, doing exactly the same as it did before. After the second run, the items will still not be properly sorted, but they will be "in a better order than they were at the end of the first run". Now imagine a list of ten thousand string items in which the first string in the list is "zzzzz". At the end of the first run it will be in position two (whereas it started off in position one). At the end of the second run it will be in position three. At the end of the third run it will be in position four, etc, etc. In general, in order to guarantee that the entire list of ten thousand items will be in the correct order you need to run through the list ten thousand times! In practice you run through the list until you reach a point where no further substitutions are required, but in the worst case that could be ten thousand times. So, in order to guarantee that you sort a list of ten thousand items you need to "make ten thousand comparisons ten thousand times"! In other words, the time taken for a simple Bubble Sort to do its work is proportional to "the square of the number of items it contains". At each iteration of the loop the individual items get nearer and nearer to their final sorted position, and specifically an item "at the bottom" which really "belongs at the top" will "bubble up" to the top as the sort progresses (hence the term "Bubble Sort"). For example, a list of 300 items will take on average nine times longer to sort than would a list of 100 items. In general, the time taken for a simple Bubble Sort is proportional to "the square of the number of items to be sorted".

Let's suppose that on a specific machine the time take to Bubble Sort a list of 300 items is 90000 microseconds. But suppose that instead of using the Bubble Sort algorithm we instead just "stabbed a guess" at the approximate "middle item in the list" (takes almost no time at all) and then ran through the entire list just once, deciding whether each specific item belonged "below the middle" or "above the middle". This would take just one run through the list and it would effectively "split the list into two halves". We could now use a simple Bubble Sort algorithm to sort "the two halves" independently, so instead of the 300 items taking 90000 microseconds, each of the two 150 items would each take 22500 microseconds (150 squared) so that the total time to sort the two "halves" would be 22500 x 2 = 45000 microsconds. (Remember, a Bubble Sort is proportioinal to the square of the number of itms being sorted). That 45000 microseconds is half of the time a simple Bubble Sort would have taken (90000 microseconds) to sort the original list. In other words, by simply running through the entire list just once (and splitting it into two smaller lists) you have cut the sorting time in half.

But why stop there? Why not just split each of the two smaller lists "in two" again (so that we end up with four smaller lists). This will again cut the overall sorting time in half.

But, again, why stop there! Why not split each of the four smaller lists into two halves again, so that we end up with eight smaller lists that we need to sort. Remember, each time we do this we cut the overall sorting time in half.

In fact, if you do this often enough then you will never have to use the Bubble Sort on the smaller lists at all, because you will eventually end up with a large number of "lists to sort" where none of them contain more than one item!

Anyway, that's the general principle of the QuickSort algorithm. It uses a kind of "divide and rule" principle, very much like the "Binary Search" algorith, which does for Searches what QuickSort does for sorts.

I've probably not really answered your question here, because I assume you were after a more detailed "here is how the code works" explanation. However, in the "sorting world" (as in most other worlds) a basic understanding of the general principles involved is usually very helpful.

Mike



.

Relevant Pages

  • How best to teach newbie at algorithms (was: coerce for arbitrary types)
    ... the algorithm itself is essentially last-in first-out, ... newbie needs to learn is how to write useful tools that go beyond ... lists, as vectors, and as structs, to show how the same API can be ... If you want to sort a list, you have to use the result of SORT. ...
    (comp.lang.lisp)
  • Re: Educated guesses for efficiency?
    ... it is comparatively rare for a program to run too slowly because an algorithm with the wrong big-O analysis was chosen. ... of things tended to be stored in lists). ... built-in sort function. ... Programmers *will* use algorithms with high complexities. ...
    (comp.lang.c)
  • Re: fastest sorted list type?
    ... implement IComparable for that class and use the default BinarySearch() ... without passing any sort of comparison to it. ... rather than the exact algorithm). ... I did have a look on google and wiki lists al the sort algorothms nicely, ...
    (microsoft.public.dotnet.languages.csharp)
  • Panic, a strange behavior of lisp program
    ... when SORT is called with a parameter that includes some that ... No actually although CLtL ... this apparent mistake in conversion from CLtL to ANSI-CL. ... Web page that lists all such "obvious" mistakes. ...
    (comp.lang.lisp)
  • RE: Incident investigation methodologies
    ... However, what sort of reaction ... Speculation gets you nowhere. ... > malware we encounter. ... > of what makes public lists useful - you can get some ...
    (Incidents)