QuickSort . I don't understand this behavior

Discussion in 'C Programming' started by camotito, Apr 24, 2006.

  1. camotito

    camotito Guest

    Hi, I want to sort an array of pointers, each position of this array
    point to a position in an integer array.
    There is a strange behavior when the 'pivot' is '0'. I am using Visual
    C++, and when executing the OS tell me "quicksort.exe has encountered
    a problem and needs to close". When there is no zeros in the integer
    array, this doesn't happen.
    The pivot is always the last element. Try to change the last element in
    the array for a non zero value and you will se it works.
    Tell me something please. Thanks

    #include <iostream>
    using namespace std;

    int *buffer[10];
    int array[10] = {4,1,14,9,2,3,6,11,8,0};

    void quicksort(int **vector, int inf, int sup)
    {
    int *temp;
    int pivot = *vector[sup];
    int i = inf-1;
    int j = sup;
    int cont = 1;

    if(inf>=sup) return;
    cout << "pivot " << pivot << endl;
    while(cont)
    {
    while(*vector[++i] < pivot);
    while(*vector[--j] > pivot);
    if(i < j)
    {
    temp = vector;
    vector = vector[j];
    vector[j] = temp;
    }
    else cont = 0;
    }
    temp = vector;
    vector = vector[sup];
    vector[sup] = temp;

    quicksort(vector, inf, i-1);
    quicksort(vector, i+1, sup);
    }

    int main()
    {
    for(int i=0; i<10; i++)
    buffer = &array;
    for(i=0; i<10; i++) cout << *buffer << " ";
    cout << endl;

    quicksort(buffer, 0, 9);

    cout << "Sorted array : " << endl;
    for(i=0; i<10; i++) cout << *buffer << " ";
    cout << endl;

    return 0;
    }
     
    camotito, Apr 24, 2006
    #1
    1. Advertising

  2. camotito

    Lew Pitcher Guest

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    camotito wrote:
    > Hi, I want to sort an array of pointers, each position of this array
    > point to a position in an integer array.
    > There is a strange behavior when the 'pivot' is '0'. I am using Visual
    > C++,


    Sorry, but C++ is off topic in comp.lang.c

    You might want to try comp.lang.c++

    > and when executing the OS tell me "quicksort.exe has encountered
    > a problem and needs to close". When there is no zeros in the integer
    > array, this doesn't happen.
    > The pivot is always the last element. Try to change the last element in
    > the array for a non zero value and you will se it works.
    > Tell me something please. Thanks
    >
    > #include <iostream>

    [snip]

    Yup. Definitely not C

    - --

    Lew Pitcher, IT Specialist, Corporate Technology Solutions,
    Enterprise Technology Solutions, TD Bank Financial Group

    (Opinions expressed here are my own, not my employer's)
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2.2 (MingW32)
    Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

    iD8DBQFETPWgagVFX4UWr64RAinNAKDJ6CTecHbTbcFKZEfh4in/ZtC1GwCgur1R
    dUDzcfgJRmVQQdjO3xJ9jlM=
    =wb/c
    -----END PGP SIGNATURE-----
     
    Lew Pitcher, Apr 24, 2006
    #2
    1. Advertising

  3. camotito

    Michael Mair Guest

    camotito schrieb:
    > Hi, I want to sort an array of pointers, each position of this array
    > point to a position in an integer array.
    > There is a strange behavior when the 'pivot' is '0'. I am using Visual
    > C++, and when executing the OS tell me "quicksort.exe has encountered
    > a problem and needs to close". When there is no zeros in the integer
    > array, this doesn't happen.
    > The pivot is always the last element. Try to change the last element in
    > the array for a non zero value and you will se it works.
    > Tell me something please. Thanks


    I will ignore the C++ specific stuff; read the comp.lang.c++
    FAQ or post your code for code review to comp.lang.c++ -- your code
    leaves much room for improvement.

    Your problem is that you do not control the indices. Print the
    indices within the corrected loops and at the beginning of
    quicksort to see what is going wrong.

    <snip>
    >
    > void quicksort(int **vector, int inf, int sup)
    > {
    > int *temp;
    > int pivot = *vector[sup];


    You are accessing vector[sup] without having checked whether
    sup >= inf.

    > int i = inf-1;
    > int j = sup;
    > int cont = 1;
    >
    > if(inf>=sup) return;


    <snip>

    > while(cont)
    > {
    > while(*vector[++i] < pivot);
    > while(*vector[--j] > pivot);


    while (i < j && *vector[++i] < pivot);
    while (i < j && *vector[--j] > pivot);

    > if(i < j)
    > {
    > temp = vector;
    > vector = vector[j];
    > vector[j] = temp;
    > }
    > else cont = 0;
    > }
    > temp = vector;
    > vector = vector[sup];
    > vector[sup] = temp;
    >
    > quicksort(vector, inf, i-1);
    > quicksort(vector, i+1, sup);


    quicksort(vector, inf, i > inf ? i-1 : inf);
    quicksort(vector, i < sup ? i+1 : sup, sup);

    > }


    <snip>

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Apr 24, 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. Sarah
    Replies:
    2
    Views:
    3,277
    Roedy Green
    Oct 23, 2003
  2. camotito
    Replies:
    2
    Views:
    525
    BigBrian
    Apr 25, 2006
  3. Heck
    Replies:
    9
    Views:
    400
  4. Ben Thomas
    Replies:
    2
    Views:
    354
    Triple-DES
    Jun 20, 2008
  5. Martin P. Hellwig
    Replies:
    1
    Views:
    380
    Martin P. Hellwig
    Mar 26, 2010
Loading...

Share This Page