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

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

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]);
}

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.

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.