Re: about quick-sort using c
- From: "Bill Pursell" <bill.pursell@xxxxxxxxx>
- Date: 16 Apr 2006 06:06:32 -0700
pinkfog wrote:
Hello,all
I m just a newbie to c,and now i m learning quick sorting,i dont very
undertand this algorrithm,can someone kind to explain it to me?
the code:
<quote>
void quick_sort(int a[] ,int low ,int high)
{
int i =low;
int j =high ;
int t= a[i];
while(i<j)
{
while(i<j&&a[j]>t)
j--;
a[i] =a[j];
while(i<j&&a[i]<=t)
i++;
a[j] =a[i];
a[i] =t;
quick_sort(a,low,i-1);
quick_sort(a,i+1,high);
}
}
<quote>
why does the code do this, esp. after the second while-statement the
assignment"a[i]=a[j]",and the third while-statement the assignment
"a[j] =a[i]"?
I m very confused.Any reply is appreciated.Thanks.
You're question isn't really about C, but it's about the algorithm.
One way to view it is that it is breaking the list into 2 pieces based
on the first entry. One piece has entries that are all less than the
first, and the 2nd piece has entries all greater than the first (that's
not quite true, but I think it makes it easier to grok the solution if
you think that way temporarily.) It might be instructive to consider a
simple example. Suppose your list has 10 entries:
3,2,0,8,7,5,1,4,9,6
The first loop moves j down until a[j]==1, then the assiigment a[i] =
a[j] creates:
1,2,0,8,7,5,1,4,9,6
You now increment i until a[i] == 8, and the assignment a[j]= a[i]
makes:
1,2,0,8,7,5,8,4,9,6
Now, a[i] = t makes the list:
1,2,0,3,7,5,8,4,6
The net effect is that the value that was at the start of the list (3)
is now in the middle of the list and the list has the property that
everything to the left of the 3 is less than 3 and everything to the
right of the three is greater than 3. You then recursively sort each
half.
Now, what I said above is not quite correct. For this case, it happens
that the list satisifies the very nice property of being ordered w.r.t.
the first entry. However, you'll notice that we never looked at the 7
or the 5. Suppose the 5 had been a 2 instead. In that case, the list
would now look like:
1,2,0,3,7,2,8,4,6.
After you do the recursion, the list will look like:
0,1,2,3,2,4,6,7,8,
with i indexing the 3 and j indexing the 6. Notice that outside of
those bounds, the list is ordered correctly. The purpose of the outer
while loop is to squeeze i and j together until the entire list is
ordered properly.
.
- Follow-Ups:
- Re: about quick-sort using c
- From: pinkfog
- Re: about quick-sort using c
- References:
- about quick-sort using c
- From: pinkfog
- about quick-sort using c
- Prev by Date: Re: shift question
- Next by Date: Re: Microsoft Quick+insertion
- Previous by thread: about quick-sort using c
- Next by thread: Re: about quick-sort using c
- Index(es):
Relevant Pages
|
