sweish - 1 year ago 103
C++ Question

# Quick Sort Implementation (Test for failure) in C++

I've given an assignment to implement Quicksort in C++, and I've successfully written code that seems to work. As I tested my algorithm for failure, it crashed when I had it sort numbers in a binary file with a million elements. Note that I have two files with one million elements each. One of them is unsorted, and the other is "almost sorted", and my algorithm seems to only fail when sorting the "almost sorted" file. Here's what my code looks like:

int partition(int arr[], int low, int high)
{
int pivotI = low; //pivot index
int pivot = arr[pivotI];
int temp = arr[low];
arr[low] = pivot;
arr[pivotI] = temp;
int partitionI = low;
low++;
while (low <= high)
{
if (arr[low] >= pivot)
{
if (arr[high] <= pivot)
{
temp = arr[high];
arr[high] = arr[low];
arr[low] = temp;
low++;
}
high--;
}
else if (arr[high] <= pivot)
{
low++;
}
else
{
low++;
high--;
}
}
if (low == high)
{
if (arr[low - 1] < pivot)
{
temp = arr[low];
}
else
{
temp = arr[low - 1];
}
}
else
{
temp = arr[high];
}
arr[high] = arr[partitionI];
arr[partitionI] = temp;
return high;
}

void quickSort(int arr[], int left, int right)
{
if (left < right)
{
int p = partition(arr, left, right);
quickSort(arr, left, p);
quickSort(arr, p + 1, right);
}
}

*I get a stack overflow error when I run said "almost sorted" binary file. Any idea why this is happening?
Thanks