CODEWITHSUNDEEP
c++algorithmsorting
maksym
maksym

Reputation: 5

Quicksort's strange behaviour when sorting descending-ascending data

Why this implementation of qs works as below, when sorting array containings numbers in descending-ascending order (100, 99, .., 0, 99, 100)?:

time for 50000 elements: 0.123 s
time for 100000 elements: 0.288 s
time for 150000 elements: 0.629 s
time for 200000 elements: 0.695 s
time for 250000 elements: 1.652 s
time for 300000 elements: 1.663 s
time for 350000 elements: 3.404 s
time for 400000 elements: 4.185 s
time for 450000 elements: 3.887 s
time for 500000 elements: 6.73 s
time for 550000 elements: 8.887 s
time for 600000 elements: 9.137 s
time for 650000 elements: 11.094 s
time for 700000 elements: 8.436 s
time for 750000 elements: 15.182 s

It works faster for 700000 elements than for 650000 elements. I repeated the test several times. Here is the code:

    #include <iostream>
    #include <cstdlib>
    #include <time.h>
    #include <new>
    #include <math.h>

    using namespace std;
    inline void swap (int *a, int *b)
    {
        int tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
    void quick_sort(int tab[], int l, int r);
    int *allocate (int size);
    void dec_inc (int tab[], const int length);
    int main()
    {
        int step = 50000;
        int how_many = 15;
        int k = 1;
        int length = step * how_many;
        int *tab = allocate(length);
        clock_t t2, t1;
        long double dif;
        while (step * k <= length)
        {
            dec_inc(tab, step*k);
            t1 = clock();
            quick_sort(tab, 0, step*k - 1);
            t2 = clock();
            dif = (long double)(t2 - t1)/CLOCKS_PER_SEC;
            cout << "time for " << step * k << " elements: " << dif << " s" << endl;
            k++;
        }
        delete [] tab;
        system("pause");

    }
    int *allocate (int size)
    {
        try
        {
            return new int [size];
        }
        catch(bad_alloc)
        {
            cerr << "ERROR\n";
            exit(EXIT_FAILURE);
        }
    }
    void quick_sort(int tab[], int l, int r)
    {
        int v = tab[(l+r)/2];
        int i = l;
        int j = r;
        do
        {
            while(tab[i] < v) i++;
            while(tab[j] > v) j--;
            if (i <= j)
            {
                swap(&tab[i], &tab[j]);
                i++, j--;
            }
        }
        while(i <= j);
        if (l < j)
            quick_sort(tab, l, j);
        if(i < r)
            quick_sort(tab, i, r);
    }
    void dec_inc (int tab[], const int length)
    {
        int i = length/2;
        for (int j = 0; j < length/2; j++, i--)
        {
            tab[j] = i;
        }
        for (int j = length/2; j < length; j++, i++)
        {
            tab[j] = i;
        }
    }

Upvotes: 0

Views: 115

Answers (1)

Peter Barmettler
Peter Barmettler

Reputation: 611

One of the drawbacks of using quicksort is its stability. Certain data sets need more steps to be sorted than others. For pathological cases it may even scale as O(n^2). I measured the number of comparisons performed by quicksort for your test data and saw that at with 700000 steps there are less comparisons to be performed than with 650000 elements. Even though your data sets seem similar, apparently for quicksort they are not. There are ways to improve quicksort's stability, see for example Programming Pearls.

Here are the measurements:

time for 650000 elements: 4.41251 s. num. comparisions 5061169826

time for 700000 elements: 3.37787 s. num. comparisions 3824058435

time for 750000 elements: 6.07856 s. num. comparisions 6900645055

And here the corresponding code: gist

Upvotes: 2

Related Questions