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.