Quick sort

[aditdano]

I have a problem with this code :

#include<iostream>
using namespace std;
void qsort(int A[], int len)
{
    if(len>=2){
    int l=0;
    int u=len-1;
    int pivot=A[rand()%len];
    while(l<u)
    {
        while(A[l]<pivot)l++;
        while(A[u]>pivot)u--;
        swap(A[l], A[u]);
    }
    qsort(A,l);
    qsort(&A[l+1],len-l-1);
    }
    else{return;}
}

void swap(int a, int b)
{
    int temp;

    temp=a;
    a=b;
    b=temp;
}

void printlist(int l[],int len)
{
    int i;
    for(i=0;i<len;i++)
    {
        cout<<l[i]<<endl;
    }
}

int main(int argc, char *argv[])
{
    int list[12]={333,250,323,12,9,900,0,732,56,88,72,12};
    printlist(list,12);
    cout<<endl;
    qsort(list,12);
    printlist(list,12);
    return 0;
}

It’s working well if the element of array <=11, if more than 11 the program will crash, can anybody find the problem..
Sorry for my horrible english...

[jaskij]

It is probably an error in your implementation, I'm not going to look for the particular cause, just list all the things I find (more or less) wrong in your code.

1. Use vectors!

2. Are you aware, that your swap function does NOTHING? Really. It works on local copies. You need pointers ore references there, like void swap(int& a,int& b)

3. You should not pick a pivot at random. Quicksort works well, if each recurring call takes in half of the numbers. So pivot should be a median

4. The swapping is not well done. The way you do it, it will be [tex]O(n^2)[/tex] if not [tex]O(n^3)[/tex]. So you could as well make a bubble sort.

5. I just noticed there is a pretty good pseudocode (for both copying and in-place algos) on the English Wiki