quicksort segmentation fault for partly sorted arrays of size 500000

Question

I have to write and test quicksort for arrays which are sorted in 25%, 50%, 75%, 95%, 99% and 99.7% and when it is filled randomly. When I use array of size 500k my program go through random array and 25% sorted array without any problem(but 25% sorted array takes it 158s) but for 50% sorted array it throw segmentation fault and "Process returned 139(0x8b)." For smaller arrays, for example 100k, even sorted, everything works. How I generate my arrays( parameter "zakres" isn't needed, I know):

    void generujTablice(int zakres,float sorted, int size_of_array)
    {
        Tablica = new int[size_of_array];           //allocating space for array
        if(sorted == -1)                            //when array have to be sorted, but inverted
            for(int i=0;i<size_of_array;i++)
                Tablica[i] = size_of_array-i;
        else
        {
            for(int i=0;i<sorted * size_of_array;i++)   //example: if sorted is 0.25 array have to be sorted in 25% from beginning
                Tablica[i] = i;
            for(int i=sorted * size_of_array;i<size_of_array;i++)  //rest of array is filled randomly but values have to be bigger than these in sorted part of array
                Tablica[i] = rand()%int(size_of_array)+sorted * size_of_array;
        }
    }

And my quicksort: (Note: I am choosing the first element as a pivot, because I want to check the worst case of algorithm. I have commented line with randomly mixing first element with another one, and when I use this swap everything works fine and very very quickly. lewy == left, prawy == right)

#include <algorithm>
void quicksort(int * Tablica, int lewy,  int prawy)
{
    if(lewy<prawy)
    {
        //swap( Tablica[lewy], Tablica[rand()%(prawy-lewy)+lewy]);
        int x = Tablica[lewy];
        int i = lewy, j = prawy;
        do{
            while(Tablica[i] < x ) i++;
            while(Tablica[j] > x ) j--;
            if( i<=j )   swap( Tablica[i++], Tablica[j--] );
        }while(i<=j);
        quicksort(Tablica,lewy,j);
        quicksort(Tablica,i,prawy);
    }
}

I am using ubuntu. I tried to google what is wrong, but it seems to me that my algorithm is almost identical to some of these I found, so I have no idea how I can fix it. Sorry for my english, unfortunately, I am not using it very often.

Thanks for helping me.

Answer 1

Since you're choosing the first element as the pivot, your recursion is going too deep; you run out of stack and crash and burn. With a large part of the data in sorted order, you are partitioning about the smallest element in the array, so your QuickSort is going to be working in quadratic time. You could improve the chances of your code surviving by recursing on the smaller partition and then looping to sort the larger partition.

You can demonstrate this by instrumenting your sort code, incrementing and printing a counter each time you enter the sort, and decrementing it when you leave. With the smaller array sizes and less pre-sorted material, you don't go as deep; with the big array size and more ordered data, you just overflow your stack.

Here's a C Quick Sort function that uses the smallest element as the pivot and iterates and recurses:

/* Fat pivot algorithm with tail recursion replaced by loop */
/* Pivot is low element */
static void fpquicksort3(Data a[], size_t low, size_t high)
{
    sort_enter(__func__, a, low, high);

    while (low + 1 < high)
    {
        Data pivot = a[low];
        size_t i = low + 1;
        size_t j = high;
        size_t k = high;
        while (i < j)
        {
            inc_comps();
            if (a[i] < pivot)
                i++;
            else if (a[i] > pivot)
            {
                if (--j != --k || i != k || i != k)
                    sort_swap3(__func__, a, i, j, k);
            }
            else
            {
                if (i != --j)
                    sort_swap2(a, i, j);
            }
        }
        if (low != --i)
            sort_swap2(a, low, i);
        if (i - low <= high - k)
        {
            if (i - low > 1)
                fpquicksort3(a, low, i);
            low = k;
        }
        else
        {
            if (k - high > 1)
                fpquicksort3(a, k, high);
            high = i;
        }
    }
    sort_exit(__func__, a, low, high);
}

The sort_enter, sort_exit, sort_swap2, sort_swap3 and inc_comps functions are instrumentation hooks in the code this came from (they do things like count the depth of recursion).

Answer 2

I'm missing a range check or sentinel value here

while(Tablica[i] < x ) i++;
while(Tablica[j] > x ) j--;

So, a segmentation fault might occur on leaving the allocated bounds.