Sorting large arrays (QuickSort) - segmentation fault

Question

For this program I am creating an array of random integers, dividing that array into two or four parts, sorting each part, and combining them back into a sorted array. The insertion sort portion of the program works for the size of arrays I need. The problem is with the quick sort. It only works with arrays up to about 3 million integers in size. I need it to work with arrays up to 100 million integers in size. Currently above 3 million it gives me a "segmentation fault(core dumped)" error. Below that 3 million it seems to work. Does anyone see the issue? I assume something is overflowing. If you look below you can see several malloc declarations, my attempt at fixing the problem. That does not seem to work.

Edit: I did a little debugging and commented out the contents of the "if (s_type == 'Q')" portion of my code. It still gave me the segmentation fault for a large array.

void insertion_sort (int ar[], int size) {
    int c, d, t;
    for (c = 1; c <= size - 1; c++){
        d = c;

        while(d > 0 && ar[d] < ar[d - 1]) {
            t = ar[d];
            ar[d] = ar[d - 1];
            ar[d - 1] = t;

            d--;
        }
    }
}

void quick_sort (int *a, int n) {
    int i, j, p, t;
    if(n < 2)
        return;
    p = a[n / 2];
    for (i = 0, j = n - 1;; i++, j--) {
        while (a[i] < p)
            i++;
        while (p < a[j])
            j--;
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        }
        quick_sort(a, i);
        quick_sort(a + i, n - i);
}

void check_sort (int ara[], int size_t) {
    int b;
    int c_i;

    c_i = 0;

    for  (b = 1; b < size_t; b++) {
        if (ara[b - 1] > ara[b]) {
            printf("Array is not sorted correctly\n");  
            break;
        } else {
            c_i++;
        }
    }

    if (c_i == size_t - 1) {
        printf("Array is sorted correctly\n");
    }
}

void combine_array(int a_ar[], int b_ar[], int c_ar[], int size_1, int size_2) {
    int i, j, k;
    i = 0;
    j = 0;
    k = 0;

    while (i < size_1 && j < size_2) {
        if (a_ar[i] < b_ar[j]) {
            c_ar[k] = a_ar[i];
            i++;
        } else {
            c_ar[k] = b_ar[j];
            j++;
        }
        k++;
    }

    if (i >= size_1) {
        while (j < size_2) {
            c_ar[k] = b_ar[j];
            j++;
            k++;
        }
    }

    if (j >= size_2) {
        while (i < size_1) {
            c_ar[k] = a_ar[i];
            i++;
            k++;
        }
    }
}

long gRefTime;

long GetMilliSecondTime(struct timeb timeBuf) {
    long mliScndTime;
    mliScndTime = timeBuf.time;
    mliScndTime *= 1000;
    mliScndTime += timeBuf.millitm;
    return mliScndTime;
}

long GetCurrentTime(void) {
    long crntTime=0;
    struct timeb timeBuf;
    ftime(&timeBuf);
    crntTime = GetMilliSecondTime(timeBuf);
    return crntTime;
}

void SetTime(void) {
    gRefTime = GetCurrentTime();
}

long GetTime(void) {
    long crntTime = GetCurrentTime();
    return (crntTime - gRefTime);
}

int main (int argc, char *argv[]) {
    int a_size, t_num;
    char s_type;
    int i, j, k; 
    int two_s[1];
    int four_s[3];

    a_size = atoi(argv[1]);
    t_num = atoi(argv[2]);
    s_type = argv[3][0];

    pthread_t tid[t_num];
    pthread_attr_t attr;    

    struct sort_2 {
        int array_ss[(a_size/2)];
        int arr_s;
    };

    struct sort_2 firstS;
    struct sort_2 firstS1;

    int *array_m = malloc(a_size * sizeof(*array_m));

    for (i = 0; i < a_size; i++) {
        array_m[i] = rand();
    }

    //for (i = 0; i < a_size; i++) {
        //printf("%d \n", array_m[i]);
    //}

    printf("\n");

    if (t_num == 2) {
        two_s[0] = ((a_size/2));
        two_s[1] = (a_size);
        int *array_s1 = malloc(two_s[0] * sizeof(*array_s1));
        int *array_s2 = malloc(two_s[0] * sizeof(*array_s2));

        printf("First half \n");

        for (j = 0; j < two_s[0]; j ++) {
            array_s1[j] = array_m[j];
            //printf("%d \n", array_s1[j]);
        }

        printf("Second half \n");

        for (k = two_s[0]; k < two_s[1]; k++) {
            array_s2[k - two_s[0]] = array_m[k];
            //printf("%d \n", array_s2[k - two_s[0]]);
        }

    printf("\n");

    check_sort(array_m, a_size);

    if (s_type == 'I') { //Insertion sort

        SetTime();

        insertion_sort(array_s1, two_s[0]);
        insertion_sort(array_s2, two_s[0]);

        printf("Sorted first half \n");

        for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s1[i]);
        }

        printf("Sorted second half \n");

        for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s2[i]);
        }       

        combine_array(array_s1, array_s2, array_m, two_s[0], two_s[0]);

        printf("Time to sort and combine: %f \n", (GetTime()));

        printf("\n");

        printf("Combined and sorted sequentially via Insertion Sort \n");

        for (i = 0; i < a_size; i++) {
            //printf("%d \n", array_m[i]);
        }

        check_sort(array_m, a_size);

        //Start of thread section

        for (i = 0; i < a_size; i++) {
            array_m[i] = rand();
        }

        printf("First half \n");

        for (j = 0; j < two_s[0]; j ++) {
            array_s1[j] = array_m[j];
            firstS.array_ss[j] = array_s1[j];
        }

        firstS.arr_s = two_s[0];

        printf("Second half \n");

        for (k = two_s[0]; k < two_s[1]; k++) {
            array_s2[k - two_s[0]] = array_m[k];
            firstS1.array_ss[k] = array_s2[k - two_s[0]];
        }

        firstS1.arr_s = two_s[0];   

        //pthread_attr_init(&attr);
        //pthread_create(&tid, &attr, insertion_sort, *firstS);         
    }

    if (s_type == 'Q') { //Quick sort

        SetTime();

        quick_sort(array_s1, two_s[0]);
        quick_sort(array_s2, two_s[0]);

        printf("Sorted first half \n");

        for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s1[i]);
        }

        printf("Sorted second half \n");

        for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s2[i]);
        }       

        combine_array(array_s1, array_s2, array_m, two_s[0], two_s[0]);

        printf("Time to sort and combine: %f \n", (GetTime()));

        printf("\n");

        printf("Combined and sorted sequentially via Quick Sort \n");

        for (i = 0; i < a_size; i++) {
            //printf("%d \n", array_m[i]);
        }

        check_sort(array_m, a_size);

        for (i = 0; i < a_size; i++) {
            array_m[i] = rand();
        }       
    }
    }

    //Four part array

    if (t_num == 4) {
        two_s[0] = ((a_size/2));
        two_s[1] = (a_size);
        four_s[0] = ((a_size/4));
        //two_s[1] = (a_size);
        int *array_s14 = malloc(four_s[0] * sizeof(array_s14));
        int *array_s24 = malloc(four_s[0] * sizeof(array_s24));
        int *array_s34 = malloc(four_s[0] * sizeof(array_s34));
        int *array_s44 = malloc(four_s[0] * sizeof(array_s44));
        int *array_14 = malloc(two_s[0] * sizeof(array_14));
        int *array_24 = malloc(two_s[0] * sizeof(array_24));

        printf("First quarter \n");

        for (j = 0; j < four_s[0]; j++) {
            array_s14[j] = array_m[j];
            //printf("%d \n", array_s14[j]);
        }

        printf("Second quarter \n");

        for (k = 0; k < four_s[0]; k++) {
            array_s24[k] = array_m[k + four_s[0]];
            //printf("%d \n", array_s24[k]);
        }

        printf("Third quarter \n");

        for (j = 0; j < four_s[0]; j++) {
            array_s34[j] = array_m[j + (2 * four_s[0])];
            //printf("%d \n", array_s34[j]);
        }

        printf("Fourth quarter \n");

        for (k = 0; k < four_s[0]; k++) {
            array_s44[k] = array_m[k + (3 * four_s[0])];
            //printf("%d \n", array_s44[k]);
        }

    printf("\n");

    check_sort(array_m, a_size);

    if (s_type == 'I') { //Insertion sort

        SetTime();

        insertion_sort(array_s14, four_s[0]);
        printf("Sorted first quarter \n");
        insertion_sort(array_s24, four_s[0]);
        printf("Sorted second quarter \n");
        insertion_sort(array_s34, four_s[0]);
        printf("Sorted third quarter \n");
        insertion_sort(array_s44, four_s[0]);
        printf("Sorted fourth quater \n");      

        //printf("Sorted first half \n");

        //for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s1[i]);
        //}

        //printf("Sorted second half \n");

        //for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s2[i]);
        //}     

        combine_array(array_s14, array_s24, array_14, four_s[0], four_s[0]);
        combine_array(array_s34, array_s44, array_24, four_s[0], four_s[0]);
        combine_array(array_14, array_24, array_m, two_s[0], two_s[0]); 

        printf("Time to sort and combine: %f \n", (GetTime()));

        printf("\n");

        printf("Combined and sorted sequentially via Insertion Sort \n");

        for (i = 0; i < a_size; i++) {
            //printf("%d \n", array_m[i]);
        }

        check_sort(array_m, a_size);

        //Start of thread section

/*      for (i = 0; i < a_size; i++) {
            array_m[i] = rand();
        }

        printf("First half \n");

        for (j = 0; j < two_s[0]; j ++) {
            array_s1[j] = array_m[j];
            firstS.array_ss[j] = array_s1[j];
        }

        firstS.arr_s = two_s[0];

        printf("Second half \n");

        for (k = two_s[0]; k < two_s[1]; k++) {
            array_s2[k - two_s[0]] = array_m[k];
            firstS1.array_ss[k] = array_s2[k - two_s[0]];
        }

        firstS1.arr_s = two_s[0];    */

        //pthread_attr_init(&attr);
        //pthread_create(&tid, &attr, insertion_sort, *firstS);         
    }

    if (s_type == 'Q') { //Quick sort

        SetTime();

        quick_sort(array_s14, four_s[0]);
        printf("Sorted first quarter \n");
        quick_sort(array_s24, four_s[0]);
        printf("Sorted second quarter \n");
        quick_sort(array_s34, four_s[0]);
        printf("Sorted third quarter \n");
        quick_sort(array_s44, four_s[0]);
        printf("Sorted fourth quarter \n");     

/*      printf("Sorted first half \n");

        for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s1[i]);
        }

        printf("Sorted second half \n");

        for (i = 0; i < two_s[0]; i++) {
            //printf("%d \n", array_s2[i]);
        }    */ 

        combine_array(array_s14, array_s24, array_14, four_s[0], four_s[0]);
        combine_array(array_s34, array_s44, array_24, four_s[0], four_s[0]);
        combine_array(array_14, array_24, array_m, two_s[0], two_s[0]);

        printf("Time to sort and combine: %f \n", (GetTime()));

        printf("\n");

        printf("Combined and sorted sequentially via Quick Sort \n");

        for (i = 0; i < a_size; i++) {
            //printf("%d \n", array_m[i]);
        }

        check_sort(array_m, a_size);

        for (i = 0; i < a_size; i++) {
            array_m[i] = rand();
        }       
    }
    }   

}

Did you debuged it? Where does it give you segmentation fault? You are not freeing anything, that could be the problem. Specially if you are working with very big arrays (Maybe you're running out of memory) — Mr. E
– Mr. E, Commented Oct 13, 2015 at 14:26
I was having trouble determining where I should be freeing. Any ideas? — OakRidgejet
– OakRidgejet, Commented Oct 13, 2015 at 14:28
You can to run gcc -Wall file.c or cppcheck --enable=all file.c and see problematic places in your code. — y_ug
– y_ug, Commented Oct 13, 2015 at 14:45
Your quick_sort algorithm seems to pass with 10M entries: codepad.org/ke8Za0Kk Upping that to 100M ends up getting the process killed due to quotas. I also added a stack depth check, and it only recurses 59 times, so that isn't the issue. (though shouldn't it only recurse log2(n), i.e. ~24 times?) — Russ Schultz
– Russ Schultz, Commented Oct 13, 2015 at 14:54
All it gave me was the following: gcc -Wall assign1.c assign1.c: In function ‘main’: assign1.c:204: warning: format ‘%f’ expects type ‘double’, but argument 2 has type ‘long int’ assign1.c:358: warning: format ‘%f’ expects type ‘double’, but argument 2 has type ‘long int’ assign1.c:427: warning: format ‘%f’ expects type ‘double’, but argument 2 has type ‘long int’ assign1.c:137: warning: unused variable ‘attr’ assign1.c:136: warning: unused variable ‘tid’ assign1.c:445: warning: control reaches end of non-void function — OakRidgejet
– OakRidgejet, Commented Oct 13, 2015 at 14:56

Kotshi · Accepted Answer · 2015-10-13 14:38:38Z

1

I see two errors here, first one: You don't check the value of argc before using argv. If you give no arguments to your program, you'll end up sending undefined addresses to atoi here:

a_size = atoi(argv[1]);
t_num = atoi(argv[2]);

Second one:

    a_size = atoi(argv[1]);

atoi() returns an int which can't be superior to 2147483647 (2^31), otherwise it overflows and end up being lower than 0.

answered Oct 13, 2015 at 14:38

Kotshi

3383 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

OakRidgejet Over a year ago

Any idea how to correct the second part? During my tests I was passing it values lower than 2147483647.

Kotshi Over a year ago

So it shouldn't be a problem (Anyway, you probably don't have enough RAM to run that test). You could change it anyway by using atol() and storing it's return in a long int.

Kotshi Over a year ago

@OakRidgejet The cleanest way to me would be to check that atoi() returns a positive value.

OakRidgejet Over a year ago

Just did what you suggested. Printed the value of atoi() right after the code gets it. Worked for a size of 100, segmentation fault for 4000000.

Kotshi · Accepted Answer · 2015-10-13 15:26:03Z

0

    struct sort_2 {
    int array_ss[(a_size/2)];
    int arr_s;
};

struct sort_2 firstS;
struct sort_2 firstS1;

Here, for a_size = 3 000 000, you are asking for 12MB of RAM on the stack, wich causes your program to stackoverflow, I suggest you use malloc().

answered Oct 13, 2015 at 15:26

Kotshi

3383 silver badges15 bronze badges

2 Comments

OakRidgejet Over a year ago

I attempted to do something like this: struct sort_2 { int *array_ss = malloc((a_size/2) * sizeof(*array_ss)); int arr_s; }; but it gives me the following error: " error: expected ‘:’, ‘,’, ‘;’, ‘}’ or ‘attribute’ before ‘=’"

Kotshi Over a year ago

@OakRidgejet You're trying to call a function from a variable definition, it makes no sense. You should define the struct like this: struct sort_2 { int a*rray_ss; int arr_s; }; Then declare your variable and allocate space like this: firstS.array_ss = malloc(a_size/2 * sizeof(*firstS.array_ss));

Luis Colorado · Accepted Answer · 2015-10-15 05:58:20Z

Perhaps this program will not work on your machine, if it has a 32bit architecture. I think you cannot have a contiguous array of more than 4Gb in such a machine. On mine it runs fine:

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#define N 10000000000UL

typedef int T;

int compare(const void *_a, const void *_b)
{
    const T *a = _a, *b = _b;
    if (*a > *b) return 1;
    if (*a < *b) return -1;
    return 0;
}

int main()
{
    T *b;
    int i;

    printf("Trying %lld array (%lld bytes)\n",
            (long long)N, (long long) sizeof(T) * N);
    assert(b = malloc(sizeof(T) * N));
    printf("b = %#p\n", b);
    printf("filling\n");
    for (i = 0; i < N; i++)
        b[i] = rand();
    printf("quicksorting\n");
    qsort(b, N, sizeof(T), compare);
    for (i = 0; i < N; i++)
        printf("a[%d] = %d\n", i, b[i]);
}

You can play with different values of N and T.

Collectives™ on Stack Overflow

Sorting large arrays (QuickSort) - segmentation fault

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related