P: n/a

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,i1);
quick_sort(a,i+1,high);
}
}
<quote>
why does the code do this, esp. after the second whilestatement the
assignment"a[i]=a[j]",and the third whilestatement the assignment
"a[j] =a[i]"?
I m very confused.Any reply is appreciated.Thanks.
pinkfog  
Share this Question
P: n/a

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,i1); quick_sort(a,i+1,high); } } <quote> why does the code do this, esp. after the second whilestatement the assignment"a[i]=a[j]",and the third whilestatement 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.  
P: n/a

Bill Pursell wrote: 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,i1); quick_sort(a,i+1,high); } } <quote> why does the code do this, esp. after the second whilestatement the assignment"a[i]=a[j]",and the third whilestatement 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.
Thanks for your explaination.
pinkfog   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 3254
 replies: 2
 date asked: Apr 16 '06
