quick sort

Discussion in 'C Programming' started by aarklon@gmail.com, Apr 11, 2006.

  1. Guest

    Hi folks,

    this is the program implementing quicksort

    #include<stdio.h>
    #include<stdlib.h>
    #define swap(a,b){int t; t=a;a=b;b=t;}

    int partition(int[],int,int);
    void quicksort(int[],int,int);

    int main(void)
    {
    int a[5],i;

    for(i=0;i<5;a = (rand()%100)+1,i++);

    puts("unsorted array:: ");
    for(i=0;i<5;printf("\t%d",a),i++);

    quicksort(a,0,5);
    puts("sorted array:: ");
    for(i=0;i<5;printf("\t%d",a),i++);

    return(EXIT_SUCCESS);
    }

    void quicksort(int a[5],int p,int q)
    {
    int j;


    if(p < q)
    {
    j = partition(a,p,q+1);
    quicksort(a,p,j-1);
    //quicksort(a,j+1,q);

    }
    return;
    }

    int partition(int a[5],int m,int p)
    {
    int v = a[m], i = m, j = p;
    do
    {
    do{ i += 1;}while(a <= v && i <= p );

    do{j -= 1;}while(a[j] >= v && j >= m);

    if(i < j) swap(a,a[j]);

    }while(i <= j && i <= p);
    a[m] = a[j]; a[j] = v;
    return j;
    }

    my questions are as follows

    1)
    this program works well on some compilers(djgpp,bloodshed devc++ 4.0)
    it is not working on turboc++ version 3.0, i am getting junk values
    how to rectify this???

    2) is the commented statement in the quicksort function(
    quicksort(a,j+1,q); ) redundant


    the partitioning is based on the following algorithm

    algorithm partition(a,m,p)
    /* within a[m],a[m+1].....a[p-1] the elements are re arranged in such
    a manner that if initially t = a[m],then after completion a[q]=t for

    some q between m and p-1,a[k] <= t for m <= k < q,and a[k] >= t
    for q < k < p,q is returned,set a[p] = infinity
    */
    {
    v = a[m];i=m,j=p;
    repeat
    {
    repeat
    i = i+1;
    until(a >= v);

    repeat
    j = j-1;
    until(a[j] <= v);

    if(i < j) swap(a,a[j])

    }until(i >= j);

    a[m] = a[j];a[j]=v;
    return j;
    }
    , Apr 11, 2006
    #1
    1. Advertising

  2. Michael Mair Guest

    schrieb:
    > Hi folks,
    >
    > this is the program implementing quicksort
    >
    > #include<stdio.h>
    > #include<stdlib.h>


    > #define swap(a,b){int t; t=a;a=b;b=t;}


    If you do not need this very often, consider not using this
    macro. It is not exactly generic and does not even give much
    clarity.

    > int partition(int[],int,int);
    > void quicksort(int[],int,int);


    Note that the compiler may be able to help you better if you
    give the parameter names in the prototypes.
    The above is the same as
    int partition(int *,int,int);
    void quicksort(int *,int,int);
    which has the advantage of making it clear that you work with
    pointers.

    > int main(void)
    > {
    > int a[5],i;
    >
    > for(i=0;i<5;a = (rand()%100)+1,i++);


    5 is a magic number here, consider using a symbolic constant
    (via #define ARRAY_SIZE 5 or similar) instead.
    The above is the same as
    for(i=0;i<5;i++)
    a = (rand()%100)+1;
    which certainly is easier to grasp at one glance.

    >
    > puts("unsorted array:: ");
    > for(i=0;i<5;printf("\t%d",a),i++);
    >
    > quicksort(a,0,5);


    This seems to imply that quicksort sorts a from 0 to 5-1.

    > puts("sorted array:: ");
    > for(i=0;i<5;printf("\t%d",a),i++);
    >
    > return(EXIT_SUCCESS);


    I would have written a printIntArray(int *array, size_t size)
    and a populateIntArray(int *array, size_t size) function such
    that main() only obtains the input, calls populateIntArray(),
    printIntArray(), quicksort() (yes, I'd have called it something
    with Int), and printIntArray() and returns finally.

    > }
    >
    > void quicksort(int a[5],int p,int q)


    The 5 has no meaning whatsoever, so just leave it out.

    > {
    > int j;
    >
    >
    > if(p < q)
    > {
    > j = partition(a,p,q+1);


    The above call seems to have implied that "q" is an exclusive
    upper array index -- seeing "q+1" passed to partition() does not
    exactly fill me with confidence.

    > quicksort(a,p,j-1);
    > //quicksort(a,j+1,q);


    Why do you not want to sort the upper half of the respective
    array? Read up on quicksort, especially the "hard split, easy
    join" part.

    >
    > }
    > return;
    > }
    >
    > int partition(int a[5],int m,int p)


    Same as above.

    > {
    > int v = a[m], i = m, j = p;
    > do
    > {
    > do{ i += 1;}while(a <= v && i <= p );
    >
    > do{j -= 1;}while(a[j] >= v && j >= m);
    >
    > if(i < j) swap(a,a[j]);
    >
    > }while(i <= j && i <= p);


    Oh, it gets just better: In this case, p is potentially
    an inclusive upper bound which in principle could make
    access to a[6] possible while even a[5] is beyond the
    array bounds.

    What happens if you pass in m==0, p==0 or m==upper, p==upper?
    You access a[-1] or a[upper+1] respectively -- this must not
    happen.

    > a[m] = a[j]; a[j] = v;
    > return j;
    > }
    >
    > my questions are as follows
    >
    > 1)
    > this program works well on some compilers(djgpp,bloodshed devc++ 4.0)
    > it is not working on turboc++ version 3.0, i am getting junk values
    > how to rectify this???


    Write a working algorithm.

    You do not seed rand() with a random value via srand(), so you get
    the same values all the time. Usually one seeds with "time(NULL)".

    Take pen and paper and work through your algorithm for array sizes
    1, 2, ..., 7, 8 and 16 for values in ascending order, values in
    descending order, all the same values, one mixed example with an
    ascending series on the even and a descending series on the odd
    elements with two elements of equal value.


    > 2) is the commented statement in the quicksort function(
    > quicksort(a,j+1,q); ) redundant


    No. You effectively sort only one or two numbers correctly, the
    rest is only grouped accordingly.

    Example: 4,5,6,7,8,3,2,1 will be partitioned how if your
    partitioning is implemented in one correct manner?
    {1,2,3}{4}{8,7,6,5} and {}{1}{3,2}{4}{8,7,6,5} by a second
    step -- this will be the sorted order.


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Apr 12, 2006
    #2
    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:
    856
  2. Eva
    Replies:
    12
    Views:
    2,600
    Rich Grise
    Aug 23, 2004
  3. John
    Replies:
    1
    Views:
    328
    Ivan Vecerina
    Apr 16, 2005
  4. John
    Replies:
    4
    Views:
    363
    Richard Herring
    Apr 19, 2005
  5. Navin
    Replies:
    1
    Views:
    671
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page