Why am I getting segmentation fault when reversed sorted array is given as input?

Question

I am testing it for various distributions and I am getting segmentation fault when reversed (descending) sorted array is given as input. Sometimes it works well even for reversed sorted array and sometimes I am getting segmentation fault error particularly on large reversed sorted array (>100000). Is it because of very deep recursive call if so then what is the limit of recursive call depth, on what factors does it depend and what precautions need to be taken care while writing recursive programs.

int partation(double *a, int lower, int upper) {
    int i = lower, j = upper;
    double t = a[lower], temp;
    while (i <= j) {
        while (i <= upper && a[i] <= t)
            i++;
        while (a[j] > t)
            j--;
        if (i <= j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
    return j;
}

void quick_sort(double *a, int lower, int upper) {
    int j;
    if (lower >= upper)
        return;
    else {
        j = partation(a, lower, upper);
        quick_sort(a, lower, j - 1);
        quick_sort(a, j + 1, upper);
    }
}

Time to learn how to use gdb, Looks like j can be negative here while(a[j]>t) j--; — Ôrel
– Ôrel, Commented Sep 25, 2017 at 6:41
I don't think j can be negative as first element is chosen as a pivot so it cannot go lower than first element this loop while(a[j]>t) j--; is sure to exit when j reduced to first index. — CJ Koirala
– CJ Koirala, Commented Sep 25, 2017 at 6:49

chqrlie · Accepted Answer · 2017-09-25 11:13:28Z

You have a segmentation fault because of a stack overflow.

A reverse sorted array is the worst case for your partition scheme: you recurse n-1 times on an array of n elements.

You can try and improve the partition scheme to avoid this pathological case, but there is a way to avoid deep recursion in the quick_sort function: on recurse on the smaller half and loop on the larger one. The pathological case will just be very slow but no longer crash.

Here is the code:

#include <stdio.h>
#include <time.h>

int partition(double *a, int lower, int upper) {
    /* assuming lower < upper */
    int i = lower, j = upper;
    double t = a[lower], temp;
    while (i <= j) {
        while (i <= upper && a[i] <= t)
            i++;
        while (a[j] > t)
            j--;
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
    return j;
}

void quick_sort(double *a, int lower, int upper) {
    while (lower < upper) {
        int j = partition(a, lower, upper);
        if (j - lower < upper - j) {
            if (lower < j - 1) {
                quick_sort(a, lower, j - 1);
            }
            lower = j + 1;
        } else {
            if (j + 1 < upper) {
                quick_sort(a, j + 1, upper);
            }
            upper = j - 1;
        }
    }
}

int main(void) {
    double a[65536];
    for (int n = 2; n <= (int)(sizeof(a) / sizeof(*a)); n += n) {
        for (int i = 0; i < n; i++) {
            a[i] = n - i;
        }
        clock_t t = clock();
        quick_sort(a, 0, n - 1);
        t = clock() - t;
        for (int i = 1; i < n; i++) {
            if (a[i - 1] > a[i]) {
                printf("out of order at %d: %f > %f\n", i - 1, a[i - 1], a[i]);
                return 1;
            }
        }
        printf("a[%d] sorted in %.3f msec\n", n, (double)t * 1000.0 / CLOCKS_PER_SEC);
    }
    return 0;
}

Output:

a[2] sorted in 0.002 msec
a[4] sorted in 0.001 msec
a[8] sorted in 0.001 msec
a[16] sorted in 0.001 msec
a[32] sorted in 0.000 msec
a[64] sorted in 0.002 msec
a[128] sorted in 0.006 msec
a[256] sorted in 0.021 msec
a[512] sorted in 0.074 msec
a[1024] sorted in 0.287 msec
a[2048] sorted in 1.185 msec
a[4096] sorted in 5.104 msec
a[8192] sorted in 19.497 msec
a[16384] sorted in 78.140 msec
a[32768] sorted in 297.297 msec
a[65536] sorted in 1175.032 msec

Regarding your second question, what factors does it depend on and what precautions need to be taken while writing recursive programs? there is no definitive answer:

The limits on stack space (if there is such a concept) are implementation specific, different systems have very different limits: from just a few kilobytes on small embedded systems to several megabytes on large systems.
Recursing thousands of times is risky, and so is defining large arrays with automatic storage. In the above code, I define an array of 64K doubles, it is not a problem on modern general purpose computers, but could be too much on a small digital sensor. The maximum recursion level with the recurse on smaller half approach is bounded by log(N), which is only 16 for N=65536, should be OK for all systems.

leyanpan · Accepted Answer · 2017-09-25 06:55:42Z

1

Yes, the segmentation it is because too deep recursions.

When you have a reversed array to be quick sorted in your function, the t in the partation function would always be the largest or smallest value in the realm as you always use a[lower] as the value of t. This means that the return value of partation would always be equal to upper or 'lower' when the array is reversed. This leads to a total number of (upper - lower) recursions, and would surely result in an error. To avoid this, use an random value between upper and lower instead of always using a[lower] as the value of t

#include <stdlib.h>
#include <time.h>

int partation(double *a, int lower, int upper)
{
    int i = lower, j = upper;
    double t = a[rand() % (upper - lower) + lower], temp;
    while (i <= j)
    {
        while (i <= upper&&a[i] <= t) i++;
        while (a[j]>t) j--;
        if (i <= j)
        {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
        }
    }
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
    return j;

}

void quick_sort(double *a, int lower, int upper)
{
    int j;
    if (lower >= upper) return;
    else
    {
        j = partation(a, lower, upper);
        quick_sort(a, lower, j - 1);
        quick_sort(a, j + 1, upper);
    }
}

int main()
{
    srand(time(0));
    /*input the value of a here*/
    /*double a[10000];
    for (int i = 10000 - 1, index = 0; --i;++index)
    {
        a[index] = i;
    }*/
    quick_sort(a, 0, 9999);
    return 0;
}

edited Sep 25, 2017 at 6:55

answered Sep 25, 2017 at 6:50

leyanpan

4332 silver badges9 bronze badges

2 Comments

CJ Koirala Over a year ago

You have said that it is because of large depth of recursive call. Do you mean stack overflow ,than what is the limit of recursive call depth, on what factors does it depend and what precautions need to be taken care while writing recursive programs. I am new to programming please explain me about this

leyanpan Over a year ago

It depends on the stack size that is usable by the program, so it really depends on your computer and your configuration. I would personally say that you need to be careful when the number of recursions might exceed 500 or so. Usually there is a way to avoid that deep recursions (using loops etc.).

Collectives™ on Stack Overflow

Why am I getting segmentation fault when reversed sorted array is given as input?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related