about quick-sort using c

Discussion in 'C Programming' started by pinkfog, Apr 16, 2006.

  1. pinkfog

    pinkfog Guest

    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;
    while(i<j)
    {

    while(i<j&&a[j]>t)
    j--;
    a =a[j];

    while(i<j&&a<=t)
    i++;
    a[j] =a;

    a =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=a[j]",and the third while-statement the assignment
    "a[j] =a"?
    I m very confused.Any reply is appreciated.Thanks.
    -------------------------------pinkfog---------------------------------------------
    pinkfog, Apr 16, 2006
    #1
    1. Advertising

  2. pinkfog

    Bill Pursell Guest

    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;
    > while(i<j)
    > {
    >
    > while(i<j&&a[j]>t)
    > j--;
    > a =a[j];
    >
    > while(i<j&&a<=t)
    > i++;
    > a[j] =a;
    >
    > a =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=a[j]",and the third while-statement the assignment
    > "a[j] =a"?
    > 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 =
    a[j] creates:
    1,2,0,8,7,5,1,4,9,6
    You now increment i until a == 8, and the assignment a[j]= a
    makes:
    1,2,0,8,7,5,8,4,9,6
    Now, a = 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.
    Bill Pursell, Apr 16, 2006
    #2
    1. Advertising

  3. pinkfog

    pinkfog Guest

    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;
    > > while(i<j)
    > > {
    > >
    > > while(i<j&&a[j]>t)
    > > j--;
    > > a =a[j];
    > >
    > > while(i<j&&a<=t)
    > > i++;
    > > a[j] =a;
    > >
    > > a =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=a[j]",and the third while-statement the assignment
    > > "a[j] =a"?
    > > 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 =
    > a[j] creates:
    > 1,2,0,8,7,5,1,4,9,6
    > You now increment i until a == 8, and the assignment a[j]= a
    > makes:
    > 1,2,0,8,7,5,8,4,9,6
    > Now, a = 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---------------------------------------
    pinkfog, Apr 17, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JKop
    Replies:
    11
    Views:
    850
  2. Replies:
    2
    Views:
    9,243
    Martin Honnen
    Sep 5, 2006
  3. Replies:
    7
    Views:
    722
    Stefan Arentz
    Sep 10, 2007
  4. Navin
    Replies:
    1
    Views:
    667
    Ken Schaefer
    Sep 9, 2003
  5. Domenico Discepola

    multi-field array sort using Sort::Fields method

    Domenico Discepola, Apr 27, 2004, in forum: Perl Misc
    Replies:
    6
    Views:
    290
    Uri Guttman
    Apr 28, 2004
Loading...

Share This Page