Member Avatar for Kerrai

Greetings

The quicksort i am building works for only aprox 50000 element in a list.
If i go above that i will run out of memory and the program will crash.

This is only when i use the median of three or left as my pivot element.
When i use random i can use lists up to atleast 1 million elements.

Is there a way to take care of the memory loss without the need of rewriting everything?

the pivotType is of user input and is sent along. And the array goes from nrOfElements -> 1.
If there is a need for more of my code, please do tell.

    array = (int *)malloc(nrOfElements * sizeof(int));

        void quickSort(int array[], int left, int right, int pivotType) {

            int pivotElement, i, j;

            if(left < right) {
                if (pivotType == 1)
                    pivotElement = leftPivot(array, left, right);
                if (pivotType == 2)
                     pivotElement = medianOfThreePivot(array, left, right); 
                if (pivotType == 3) 
                    pivotElement = randomPivot(array, left, right);

                i = left+1;
                j = right;


                while(i <= j) {
                    while(i <= right && array[i] <= pivotElement) 
                        i++;
                    while(j >= left && array[j] > pivotElement) 
                        j--;
                    if (i < j) 
                        swapElement(&array[i], &array[j]);
                }
                    swapElement(&array[left], &array[j]);
                    quickSort(array,left,j-1, pivotType);
                    quickSort(array,j+1,right, pivotType);

            }
        }

    //after all quicksorts are done with all subarrays the
    free(array); is called
  • 3 Contributors
  • 4 Replies
  • 480 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Kerrai

Dani AI

Generated

Quicksort running out of memory in some pivot modes almost always points to stack exhaustion from very deep recursion rather than a heap allocation bug. A pivot that repeatedly produces highly unbalanced partitions (left or a broken median-of-three) gives O(n) recursion depth; a random pivot typically avoids that, which explains why your random mode scaled farther. was right to suspect pivot choice, and ’s later discovery about the platform stack limit explains why the program crashed rather than gracefully slowing down.

If you want the smallest changes that avoid rewriting everything, limit recursion depth by always recursing on the smaller partition and looping on the larger one. Conceptually:

while (left < right) {
  p = partition(...);
  if (p - left < right - p) {
    quicksort(left, p-1);
    left = p+1;      // iterate on larger side
  } else {
    quicksort(p+1, right);
    right = p-1;
  }
}

This guarantees O(log n) stack use in the best/worst practical cases.

Other practical, non‑invasive fixes:

  • Convert the second recursive call into a loop or use an explicit heap-based stack (iterative quicksort).
  • Switch small partitions to insertion sort (threshold ~10–30) to reduce recursion.
  • Use an introsort approach (fall back to heapsort if recursion gets too deep).
  • Check your median-of-three routine: ensure the median value is actually used as the pivot and that its location matches what your partition expects.
  • Seed RNG once at program start if you use random pivots (don’t call srand repeatedly).

Finally, verify compiler/linker stack settings and test with pathological inputs (sorted, reverse-sorted, many-equals) to reproduce and confirm fixes. ’s external-sort idea is a last resort for truly huge data that won’t fit comfortably in memory.

Recommended Answers

All 4 Replies

Member Avatar for zeroliken

could you give an example of which digit is chosen for leftPivot and median of three if it's an extreme(where the digits would be placed in a skewed pattern) then there's your problem... the wrong choice of pivot
just my assumption

Member Avatar for Kerrai

I use three strategies to find the pivot element.
They are always put to the left.

int leftPivot(int array[], int left, int right) {

    return (array[left]);
}

int medianOfThreePivot(int array[], int left, int right) {
    int center = (left + right) / 2;

    if (array[left] > array[center])
        swapElement(&array[left], &array[center]);
    if (array[left] > array[right]) 
        swapElement(&array[left], &array[right]);
    if (array[center] > array[right]) 
        swapElement(&array[center], &array[right]);

    swapElement(&array[center], &array[right-1] );
    return (array[left]);
}

int randomPivot(int array[], int left, int right) {

    int pivot;

    srand ( time(NULL) );
    pivot = left+rand()%(right-left+1);
    swapElement(&array[left], &array[pivot]);

    return (array[left]);
}
Member Avatar for adityatandon

Yeah, i had the same problem... The solution i found to it, that is without using dynamic allocation, is writing all my data down into a separate file.. And then sorting the elements in the file by using functions like seekg() and tellg(). And after which u can read out the median.

Member Avatar for Kerrai

Well after tons of research i solved it

It was due to visual studio not allocating enough stack/heap memory.. so it just ran out when it did all the recursive calls on quicksort.

But i downloaded Pelles C and edited the stack reserve to 0x 1600000 .. and now i could handle lists of up to 500k elements in descending order with left pivot element.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.