1.11M Members

Quick sort crashes for random values as input

 
0
 

Hey guys, I have a problem. I created a quick sort program and it functions perfectly for quantity less than 100. I searched for errors and changed and now for more than 100 values, it runs perfectly and sometimes it hangs. I am unable to decipher whats the error. Did i make any logical errors or not.

PLease note i am taking random values each and every time. So one set of numbers generated works and the other set does not (try values in the range of 700 or 800)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;

class array
{
    private:
        int arr[3000];
        int count;
    public:
        array();
        void add( int item );
        int getcount();
        static int split(int*, int, int);
        void quicksort(int lower, int upper);
        void display();

};

array::array()
{
    count = 0;
    for(int i=0;i<3000;i++)
        arr[i]=0;
}
void array::add(int item)
{
    if(count<3000)
    {
        arr[count] = item;
        count++;
        //cout<<count<<endl;
    }
    else
        cout<<"Array is full\n";
}

int array::getcount()
{
    return count;
}

void array::quicksort(int lower, int upper)
{

    if(upper > lower)
    {

        cout<<"\t"<<lower<<"\t"<<upper<<"\n";
        int i=split(arr,lower,upper);

        quicksort(lower, i-1);
        quicksort(i+1,upper);

    }
}

int array::split(int* arr, int lower, int upper)
{
    int pivot,i,j,temp,i1,j1;

    pivot=arr[lower];
    i=lower+1;
    j=upper;
    i1=i;
    j1=j;
    while(i<j && i<=j1 && j>=i1)
    {
        while(pivot>arr[i])
        {
            i++;
        }
        while(pivot<arr[j])
        {
            j--;
        }
        if(j>i)
        {
            temp = arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        else
        {
            continue;
        }
    }
    if(j<=i)
    {


    temp = arr[lower];
    arr[lower] = arr[j];
    arr[j]=temp;
    }
    return j;
}

void array::display()
{
    cout<<endl;
    for(int i=0;i<count;i++)
        cout<<arr[i]<<"\t";
}

int main()
{
    array obj1;
    srand(time(NULL));
    cout<<"Enter the number of elements"<<endl;

    int isize,temp;
    cin>>isize;
    for(int i=0;i<isize;i++)
    {
        temp = rand() % 10000 ; // values from 1000 t0 10999
        //arr[i] = temp;
        obj1.add(temp);
    }

    int top = obj1.getcount();
    obj1.quicksort(0,top-1);
    obj1.display();
    return 0;
}
 
0
 

The problem is somewhere in your quicksort algorithm. Testing your code with 100 elements, seems to complete. BUT the output is not perfectly sorted.

Enter the number of elements
100
        0       99
        0       20
        0       1
        3       20
        3       7
        3       5
        3       4
        9       20
        9       16
        11      16
        13      16
        15      16
        18      20
        22      99
        22      41
        22      26
        22      25
        24      25
        28      41
        28      32
        29      32
        30      32
        30      31
        34      41
        34      35
        37      41
        38      41
        38      39
        43      99
        43      47
        43      45
        43      44
        49      99
        49      96
        50      96
        50      52
        54      96
        54      76
        54      57
        55      57
        59      76
        59      60
        62      76
        62      74
        62      64
        63      64
        66      74
        66      67
        69      74
        70      74
        70      72
        71      72
        78      96
        80      96
        80      84
        80      83
        82      83
        86      96
        86      91
        86      88
        87      88
        90      91
        93      96
        93      94
        98      99

39      117     363     538     420     582     587     604     679     691
849     862     986     1161    1176    1187    1179    1206    1266    1422
1702    1982    2025    2071    2076    2080    2126    2458    2471    2494
2562    2758    2820    3169    3493    3205    3532    3602    3635    3691
3989    4018    4046    4216    4065    4221    4358    4376    4392    4469
4641    4756    4781    4848    4871    4959    5002    5152    5339    5561
5516    5617    5666    5789    5828    5900    5977    5977    6169    6481
6692    6934    6743    6937    7062    7155    7283    7329    7343    7686
7737    7812    7904    7892    8040    8295    8389    8859    8756    9036
9051    9342    9379    9407    9540    9603    9627    9777    9901    9932
Press any key to continue . . .

Look at the first row... 420 is misplaced

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