How to program a quick sort function?
Thomas Dean
far. So how to program it?
If you know, could you please teach me? Thank you anyway.
Seebs
> It is said that quick sort has been the fastest sorting algorithm so
> far.
Not by anyone informed.
> So how to program it?
Ask your TA or instructor if you need help.
-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
mohangupta13
> It is said that quick sort has been the fastest sorting algorithm so
> far. So how to program it?
runtime then other comparison sorting algorithms.
> If you know, could you please teach me? Thank you anyway.
a good explanation.
I will briefly tell you the main idea .
Given a set of numbers S{ a,b,c,d,e...} choose a number randomly
(randomized quicksort) say 'd' . Now move all elements <= 'd' on the
left side of the set and all the elements >'d' on the right
side .Place 'd' between these two parts of the set. Now recursively
sort both parts.( Note at this point 'd' is fixed at a location , it
doesn't belong to either part and should not be moved ).
Example: S{ 5,2,7,1,6}
Step1: randomly choose an element say 2
Step 2: partition : s1{1}, s2{5,6,7} so that S looks like S1 2 S2
(note 2 is between S1 and S2 )
step 3: Recursively do the same with S1 ans S2 ( the base case of
recursion is : return when the set is having 0 element).
Thanks
Mohan
Eric Sosman
> It is said that quick sort has been the fastest sorting algorithm so
> far.
Only someone who doesn't know what he's talking about
would say such a thing so baldly, without qualification.
> So how to program it?
In the language of your choice. While you're still
familiarizing yourself with what's involved, it will be
helpful to use a language (like C) that allows recursive
subroutine calls.
"Engineering a Sort Function" by Bentley and McIlroy
is a must-read, but it sort of assumes you already know
something about Quicksort. Write a "baby steps" version
of your own to familiarize yourself with what's involved,
and read Bentley&McIlroy afterward.
> If you know, could you please teach me? Thank you anyway.
Homework? What do your teacher and your textbook say?
Not homework? There are lots of Quicksort explanations
on the net; GIYF.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Malcolm McLean
> It is said that quick sort has been the fastest sorting algorithm so
> far. So how to program it?
> If you know, could you please teach me? Thank you anyway.
>
http://www.personal.leeds.ac.uk/~bgy1mm
It's under the Basic Algorithms sourcecode.
An industrial quicksort switches to insertion sort or similar when the
section to sort goes under a certain lenth. There's also the annoying fact
that C doesn't have a memswap() fucntion to exchange two areas of memory
efficiently.
Beej Jorgensen
>I will briefly tell you the main idea .
Adding onto what Mohan said here, an interesting and/or important thing
to note is that once you partition around the pivot, the pivot is in its
final resting place. Here's a slightly longer example, with unsorted
data in { }:
Data to sort: { 6 3 8 4 1 0 9 7 5 2 }
1. Choose pivot as the first element, 6.
2. Partition into a set that is less than 6, and a set that is greater
than 6:
{ 3 4 1 0 5 2 } 6 { 8 9 7 }
Then you repeat the steps, recursively, on the unsorted left and right
sides. So, taking the left list (the numbers less than 6):
3. Choose pivot as the first element of { 3 4 1 0 5 2 }, namely 3.
4. Partition into a set that is less than 3, and a set that is greater
than 3:
{ 1 0 2 } 3 { 4 5 } 6 { 8 9 7 }
| |
Looking into the future, compare this with the eventually-sorted list:
| |
0 1 2 3 4 5 6 7 8 9
and you can see that 3 and 6 were in their final resting places as soon
as you were done with their partitioning. Basically, each time you
partition, you put an element in its final sorted order.
5. Keep on recursing until your sublists are too small to partition.
In the above example, I was choosing the first element in the list as
the pivot; in a vanilla Quicksort you can choose any element you want,
but the first element is convenient to grab.
-Beej
Nick Keighley
> mohangupta13 <mohangupt...@gmail.com> wrote:
> >I will briefly tell you the main idea .
>
> Adding onto what Mohan said here, an interesting and/or important thing
> to note is that once you partition around the pivot, the pivot is in its
> final resting place.
didn't he say that when he said "(Note at this point 'd' is fixed at a
location , it
doesn't belong to either part and should not be moved)"
<snip>
Beej Jorgensen
>didn't he say that when he said "(Note at this point 'd' is fixed at a
>location , it doesn't belong to either part and should not be moved)"
Curses!
Apologies, Mohan.
-Beej