CODEWITHSUNDEEP
c
Piotshe
Piotshe

Reputation: 59

Quicksort crashes with more than 500k elements

I have a problem in my pretty easy algorithm - quicksort in C. It is very efficient (about 0.1s with randomize and checking if the list is sorted) but when i want to sort more than 500k elements it crashes. Unfortunatelly i need to sort more of them because i need to write some kind of summary at the end :(

Here is my code, maybe someone will see a stupid mistake. Thanks in advance!

int quick (int a[],int begin,int end)
{
    int i = begin, j = end, w, q, pivot, k;
    q=begin+end;
    q=q/2;
    pivot=a[q];
    while (1)
    {
        while (a[j] > pivot && j>=0)
        j=j-1;
        while (a[i] < pivot && i<j)
        i=i+1;
        if (i < j)
        {
            k = a[i];
            a[i] = a[j];
            a[j] = k;
            i++;
            j--;
        }
        else
        return j;
    }
}

void quicks (int a[], int begin, int end)
{
    int x;
    if (end>begin)
    {
        x=quick(a,begin,end);
        quicks(a,begin,x);
        quicks(a,x+1,end);

    }
}

It seems that i just need to use malloc and it is working fine. Thanks a lot for Your help!

Upvotes: 3

Views: 288

Answers (2)

chmike
chmike

Reputation: 22134

Here is another and simpler implementation.

void quickSort(int a[], int begin, int end)
{
    int left = begin - 1, right = end + 1, tmp;
    const int pivot = a[(begin+end)/2];

    if (begin >= end)
        return;

    while(1)    
    {
        do right--; while(a[right] > pivot);
        do left++; while(a[left] < pivot);

        if(left < right)
        {
            tmp = a[left];
            a[left] = a[right];
            a[right] = tmp;
        }
        else 
            break;
    }
    quickSort(a, begin, right);    
    quickSort(a, right+1, end);
}

You call it like this

int main(void)
{
    int tab[5] = {5, 3, 4, 1, 2};
    int i;

    quickSort(tab, 0, 4); // 4 is index of lest element of tab

    for(i = 0; i < 5; i++)
        printf("%d ", tab[i]);
    printf("\n");

    return 0;
}

Upvotes: 1

Bruno
Bruno

Reputation: 56

You are suffering from RAM exhaustion/rollover: As you use an array of int, each of them requires 4 bytes. Your memory mapping is handled using size_t-type indexes. If you are compiling in 32-bit mode (which is probably your case), the maximum number it can get at is 2147483648 (2^31). With 4 bytes per int, you can only handle 536870912 elements (2^31 / 4).

As the system requires some RAM for other purposes (e.g. globals), you can only use a bit more than 500K entries.

Solution: Use a 64-bit compiler and you should be fine.

BR

Upvotes: 2

Related Questions