This is taken from Wikipedia, under Quicksort:
"
This close fit with modern architectures makes quicksort one of the
fastest sorting algorithms on average. Because of this excellent
average performance and simple implementation, quicksort has become one
of the most popular sorting algorithms in practical use.
"
Which isn't quite the same as my take on the original poster's
statement:
"
BUT WIKIPEDIA SAYS THAT MERGE SORT IS 30% FASTER THAN QUICK
SORT AND ANYWAYS WE USE MERGE SORT IN ONLINE SORTING AND EXTERNAL SORT,
WHERE WE HAVE THE OPTION OF APPLYING QUICKSORT,SO HOW CAN QUICK BE
BETTER. ALSO, WHERE DO HEAP SORT AND RADIX SORT FIT IN?
"
Let's be clear here: Quicksort OWNS mergesort, EXCEPT in two specific
cases:
1) Another O(n log n) sorting algorithm is used to help mergesort.
(Like Radix)
2) The sorting job requires slow access (like from a tape or hard
drive). It's an external sort.
I left out the third specific case where mergesort can beat or equal
Quicksort, because it's SOO
silly. That case is where the data to be sorted is SO well arranged for
mergesort, that it's pathetic.
Think of a list of names wherein at the first split (halfway), the two
subsets are already nearly or completely sorted,
and ready to be merged. Clearly, this oddball situation is made for
mergesort!
This BASIC program (Quickbasic) by Ethan Winer is one worth running
through a time or two, to really help
understand how the Quicksort progresses. (and why it is so fast).
'********* SEEQSORT.BAS - Quick Sort algorithm visual demonstration
'Copyright (c) 1992 Ethan Winer
DEFINT A-Z
DECLARE SUB SeeQSort (Array!())
RANDOMIZE TIMER 'generate a new series each run
CONST MaxElements = 23 'the size of the text array
CONST Delay! = 1! 'pause delay, change to suit
CONST FG = 7 'the foreground color
CONST BG = 1 'the background color
CONST Hi = 15 + 16 'high-intensity flashing
DIM Array!(1 TO MaxElements) 'create an array
FOR X = 1 TO MaxElements 'fill with random numbers
Array!(X) = RND(1) * 500 'between 0 and 500
NEXT
COLOR FG, BG
CLS
LOCATE 25, 1
PRINT "Press Escape to end the program early"; TAB(80);
CALL SeeQSort(Array!())
SUB SeeQSort (Array!()) STATIC
REDIM QStack(10) 'create a stack big enough for this example
First = LBOUND(Array!) 'initialize work variables
Last = UBOUND(Array!)
DO
DO
Temp! = Array!((Last + First) \ 2) 'seek midpoint
I = First
J = Last
DO 'reverse both < and > below to sort descending
WHILE Array!(I) < Temp!
I = I + 1
GOSUB UpdateScreen
GOSUB Pause
WEND
WHILE Array!(J) > Temp!
J = J - 1
GOSUB UpdateScreen
GOSUB Pause
WEND
IF I > J THEN EXIT DO
IF I < J THEN
LOCATE 1, 60
COLOR BG, FG
PRINT " About to swap ";
COLOR Hi, BG
LOCATE I, 39
PRINT USING "####.## "; Array!(I);
LOCATE J, 39
PRINT USING "####.## "; Array!(J);
COLOR FG, BG
GOSUB Pause
SWAP Array!(I), Array!(J)
GOSUB UpdateScreen
LOCATE 1, 60
COLOR BG, FG
PRINT " Swapped ";
GOSUB Pause
END IF
I = I + 1
J = J - 1
LOOP WHILE I <= J
IF I < Last THEN 'Done
LOCATE 1, 60
COLOR BG, FG
PRINT " About to push ";
GOSUB Pause
QStack(StackPtr) = I 'Push I
QStack(StackPtr + 1) = Last 'Push Last
StackPtr = StackPtr + 2
GOSUB UpdateScreen
LOCATE 1, 60
COLOR BG, FG
PRINT " Pushed ";
GOSUB Pause
END IF
Last = J
LOOP WHILE First < Last
IF StackPtr = 0 THEN EXIT DO
LOCATE 1, 60
COLOR BG, FG
PRINT " About to pop ";
GOSUB Pause
StackPtr = StackPtr - 2
First = QStack(StackPtr) 'Pop First
Last = QStack(StackPtr + 1) 'Pop Last
GOSUB UpdateScreen
LOCATE 1, 60
COLOR BG, FG
PRINT " Popped ";
GOSUB Pause
LOOP
ERASE QStack 'delete the stack array
COLOR FG, BG
EXIT SUB
UpdateScreen:
COLOR FG, BG
LOCATE 1, 60
PRINT SPC(15);
FOR X = 1 TO MaxElements
LOCATE X, 24
IF X = (Last + First) \ 2 THEN
COLOR BG, FG
PRINT " Midpoint ==> "
COLOR FG, BG
ELSE
PRINT SPC(14);
END IF
LOCATE X, 1
IF X = First THEN
COLOR BG, FG
PRINT " First ==> "
COLOR FG, BG
ELSE
PRINT SPC(11);
END IF
LOCATE X, 13
IF X = Last THEN
COLOR BG, FG
PRINT " Last ==> "
COLOR FG, BG
ELSE
PRINT SPC(11);
END IF
LOCATE X, 39
PRINT USING "####.## "; Array!(X);
PRINT SPC(17);
COLOR BG, FG
LOCATE X, 48
IF X = I THEN
PRINT " <== I "
END IF
IF X = J THEN
LOCATE X, 56
PRINT " <== J "
END IF
COLOR FG, BG
NEXT
RETURN
Pause:
Start! = TIMER
DO
LOOP WHILE Start! + Delay! > TIMER
IF INKEY$ = CHR$(27) THEN END
RETURN
Michael, Michael, Michael -
You were off to such a good start! <grin, grin>
"
A point which I have not seen mentioned is cache performance. One of
the big advantages that Quicksort and variants like Introsort gain over
the closest competitors such as Radix sort is that they are far more
cache friendly and this can make all the difference on modern machines.
"
So true - and so insightful.
So why this?
"
That being said, I'd put my implementation of Introsort up against any
other generic sort any day of the week. The code is a C++ template
class, freely available at
http://www.michael-maniscalco.com/sorting.htm.
- Michael A Maniscalco
"
Why Michael? Why??
I'm tempted to ask if a relative dressed you funny as a child, but I
won't!! <grin, grin, grin> j/k
Seriously, I haven't looked at your program's code yet. Must be
something that you really like in it.
Adak (The Quicksort Fan)
"The beatings will continue until morale improves."
END SUB
There are several of these around the net that I've seen over the
years.
Enjoy!
Adak
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
