Re: Detailed explanation of how a QuickSort Works
- From: "Larry Serflaten" <serflaten@xxxxxxxxxxxxxx>
- Date: Sat, 7 Apr 2007 13:36:12 -0500
"Paul MH" <paulmorrishill@xxxxxxxxxxxxxx> wrote
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.
Thanks for any responses, greatly apreciated.
It would probably be better if the explaination wasn't so detailed,
so as to get an overview of the entire process. One method to
help understand what the computer must do is to take on the role
of the computer. You pretend you are the computer, and perform
the needed operation, and then translate what you've done into
computer code. In this case it may help you understand what
the computer code is doing, if you did the process yourself....
For the quicksort algorithm, first realize that it is a recursive
algorithm. You are going to sort the data into two parts, and
then treat each part as a new set of data and call the sort operation
on those two parts. That call would sort the new data set into two
parts, and make the call again for each of those, and so on, and
so on, until the sort is complete....
To pretend you are the computer, imagine you have a list of
data laid out on a number line. Put your left index finger at the
start of the list, and your right index finger at the end of the list.
Pick one number from the list of data (most would suggest to
pull it from the middle of the list, but it need not be) The ideal
case would have you pick the mean value to key on (or the average
value of all values in the list of data) The worst case would
be picking a value that lies at either end of the spectrum, but
again, you just pick one and use it, the probability is high that
you would not pick a value from either end.
What you are going to do is move all values that are greater
than the key value to the top (right side) of the list, and all
values that are less than the key value to the bottom (left
side) of the list.
Now, with a key value obtained from the list, check the data that
is under your left index finger. If it is greater than the key value,
then stop. If not, move your left finger up one cell and test
again. Keep moving up until the value under your finger is
greater than the key value.
Now, do the same with your right index finger, if a value is
less than the key value, then stop, otherwise keep moving your
finger down the list of data.
When both fingers have stopped, you have a greater under your
left finger, and a lesser value under your right finger, so they
need to swap positions. (Pretend you swap them) Then continue
on from that point with your left finger moving up until you find
a greater value and then your right finger moving down until you
find a lesser value, so they can be swapped.
Eventually your fingers will meet. It may not always happen at the
exact center of the list, but they will meet eachother somewhere.
At that time the list is partially sorted. All the data to the left of the
meet position is less than the key value, and all the data to the
right of the meet point is greater than the key value.
From there you have two lists, divided at the meet point. Do thesame sort process with each of those two parts, placing your fingers
at the ends, picking a key value and moving toward the center,
swapping those that are out of position.
As you 'divide and conquor' the data sets keep getting smaller and
smaller, each of them partially sorted into two smaller sets. Each time
you are partially sorting the data greater or lesser than some value
from that specific set. When the data set is only one cell long, you
know that can't be sorted any further. So, to complete the sort you
keep dividing the data sets until one or both of the new sets are only
one cell long. When you've divided any part down to one cell, you
need not call the sort on that cell, and that is the turning point on
backing out of the recursion. Eventually, all the parts will be divided
down to one cell long and at that point the list is sorted.
Now that you have a general idea, read the process again and see
if it helps you sort out your thoughts!
<g>
HTH
LFS
.
- References:
- Detailed explanation of how a QuickSort Works
- From: Paul MH
- Detailed explanation of how a QuickSort Works
- Prev by Date: Re: Fun and games instaling VB6 and MSDN!
- Next by Date: Re: Detailed explanation of how a QuickSort Works
- Previous by thread: Re: Detailed explanation of how a QuickSort Works
- Next by thread: Re: Detailed explanation of how a QuickSort Works
- Index(es):
Relevant Pages
|
Loading
