Quicksort

Discussion in 'C Programming' started by Debaser, May 11, 2005.

  1. Debaser

    Debaser Guest

    Following the pseudocode from a book, I came up with the following
    code. It runs fine but does not sort properly. The swapMB function was
    added for convenience...perhaps I'm not swapping values properly(?).
    Have a look please:

    --------------

    /* Quick Sort Algorithm Implementation */
    /* Last element in (sub)array as pivot */


    #include <stdio.h>

    int partitionMB(int *A, int p, int r);
    void qsortMB(int *A, int p, int r);
    void swapMB(int* A, int x, int y);

    /* Swaps two elements in an INT array */
    void swapMB(int* A, int x, int y)
    {
    int z;

    z = A[x];
    A[x] = A[y];
    A[y] = z;
    }

    /* Recursive quicksort */
    void qsortMB(int *A, int p, int r)
    {
    int q;

    if (p < r) {
    q = partitionMB(A, p, r);
    qsortMB(A, p, q-1);
    qsortMB(A, q+1, r);
    }
    }

    /* Partions an INT array of size A[p..r] into two sub arrays */
    int partitionMB(int *A, int p, int r)
    {
    int x, /* Pivot */
    i, j; /* Array access */

    /* Pick pivot as last element in (sub)array */
    x = A[r-1];

    /* Put i at one before first element */
    i = p-1;

    /* Move elements <= pivot to current i+1 position*/
    for (j = p; j < r-2; j++) {
    if (A[j] <= x) {
    swapMB(A, ++i, j);
    }
    }

    /* Put pivot after values <= itself */
    swapMB(A, ++i, r-1);


    return i;
    }


    /* Sample main() */
    int main(void)
    {

    int A[] = {5,2,3,7,8,4,10,31,1,43};
    int x;

    qsortMB(A, 0, sizeof(A)/sizeof(int));

    for (x = 0; x < sizeof(A)/sizeof(int); x++) {
    printf("%d ", A[x]);
    }

    printf("\n");

    return 0;
    }



    ------------

    Thanks in advance.
    -Mike-
    Debaser, May 11, 2005
    #1
    1. Advertising

  2. Debaser

    pete Guest

    Debaser wrote:
    >
    > Following the pseudocode from a book, I came up with the following
    > code. It runs fine but does not sort properly. The swapMB function was
    > added for convenience...perhaps I'm not swapping values properly(?).
    > Have a look please:
    >
    > --------------
    >
    > /* Quick Sort Algorithm Implementation */
    > /* Last element in (sub)array as pivot */
    >
    > #include <stdio.h>
    >
    > int partitionMB(int *A, int p, int r);
    > void qsortMB(int *A, int p, int r);
    > void swapMB(int* A, int x, int y);
    >
    > /* Swaps two elements in an INT array */
    > void swapMB(int* A, int x, int y)
    > {
    > int z;
    >
    > z = A[x];
    > A[x] = A[y];
    > A[y] = z;
    > }
    >
    > /* Recursive quicksort */
    > void qsortMB(int *A, int p, int r)
    > {
    > int q;
    >
    > if (p < r) {
    > q = partitionMB(A, p, r);
    > qsortMB(A, p, q-1);
    > qsortMB(A, q+1, r);
    > }
    > }
    >
    > /* Partions an INT array of size A[p..r] into two sub arrays */
    > int partitionMB(int *A, int p, int r)
    > {
    > int x, /* Pivot */
    > i, j; /* Array access */
    >
    > /* Pick pivot as last element in (sub)array */
    > x = A[r-1];
    >
    > /* Put i at one before first element */
    > i = p-1;
    >
    > /* Move elements <= pivot to current i+1 position*/
    > for (j = p; j < r-2; j++) {
    > if (A[j] <= x) {
    > swapMB(A, ++i, j);
    > }
    > }
    >
    > /* Put pivot after values <= itself */
    > swapMB(A, ++i, r-1);
    >
    >
    > return i;
    > }
    >
    > /* Sample main() */
    > int main(void)
    > {
    >
    > int A[] = {5,2,3,7,8,4,10,31,1,43};
    > int x;
    >
    > qsortMB(A, 0, sizeof(A)/sizeof(int));
    >
    > for (x = 0; x < sizeof(A)/sizeof(int); x++) {
    > printf("%d ", A[x]);
    > }
    >
    > printf("\n");
    >
    > return 0;
    > }


    /* BEGIN qsortMB.c */

    #include <stdio.h>

    int partitionMB(int *A, int p, int r);
    void qsortMB(int *A, int p, int r);
    void swapMB(int* A, int x, int y);

    int main(void)
    {
    int A[] = {5,2,3,7,8,4,10,31,1,43,8,7,3,2,5};
    int x;

    qsortMB(A, 0, sizeof(A) / sizeof(int) - 1);
    for (x = 0; x < sizeof(A) / sizeof(int); x++) {
    printf("%d ", A[x]);
    }
    putchar('\n');
    return 0;
    }

    void swapMB(int* A, int x, int y)
    {
    int z;

    z = A[x];
    A[x] = A[y];
    A[y] = z;
    }

    void qsortMB(int *A, int p, int r)
    {
    int q;

    if (p < r) {
    q = partitionMB(A, p, r);
    qsortMB(A, p, q-1);
    qsortMB(A, q+1, r);
    }
    }

    int partitionMB(int *A, int p, int r)
    {
    int x, j;

    x = A[r];
    for (j = p; j < r; j++) {
    if (A[j] <= x) {
    swapMB(A, p++, j);
    }
    }
    swapMB(A, p, r);
    return p;
    }

    /* END qsortMB.c */

    --
    pete
    pete, May 12, 2005
    #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. Sarah
    Replies:
    2
    Views:
    3,242
    Roedy Green
    Oct 23, 2003
  2. hiwa
    Replies:
    4
    Views:
    633
    Esmond Pitt
    Mar 29, 2005
  3. Exekute

    c++ and quicksort

    Exekute, Sep 27, 2003, in forum: C++
    Replies:
    6
    Views:
    9,020
    Jerry Coffin
    Sep 28, 2003
  4. David Sachs

    Re: c++ and quicksort

    David Sachs, Sep 28, 2003, in forum: C++
    Replies:
    1
    Views:
    469
    Gianni Mariani
    Sep 28, 2003
  5. Alex Vinokur
    Replies:
    0
    Views:
    971
    Alex Vinokur
    Aug 30, 2004
Loading...

Share This Page