1,105,447 Community Members

Quick sort

Member Avatar
aditdano
Newbie Poster
1 post since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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...

Member Avatar
jaskij
Junior Poster
105 posts since Oct 2011
Reputation Points: 45 [?]
Q&As Helped to Solve: 19 [?]
Skill Endorsements: 0 [?]
 
0
 

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

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: