joe_04_04 joe_04_04 - 26 days ago 7
C++ Question

Looking for error in C++ Quicksort / Insertion sort combo

Im trying to build a the quicksort / insertion sort combo, as some say its fairly fast, as it tackles the larger subarrays with quicksort and the smaller arrays with insertion sort, but something is definitely not correct. I've been testing the sorting with some files I generated. I'm currently using a file of 1,000,000 numbers, with the range limit on each number being from 1 to 1,000,000. Prior to adding the insertion sort, I was able to sort the 1 million numbers in about 0.2 seconds, after adding insertion sort as a conditional if statement, I'm lucky to sort 100,000 numbers in less than 4 seconds, so I know there's an error in the code, but I can't find it. My code is just an amalgam of different online references for these types of sorting methods, I don't claim the code as my own and can provide links to the original if necessary. However, the references I used weren't written in C++ and were class-oriented, so I had to make changes, which is why I think there's an error.

void modifiedQuickSort(arrPtr &arrayPointer, int first, int last)
{
int firstTemp = first, lastTemp = last;
int temp;
int pivot = arrayPointer[(first + last) / 2];


if((last - first) < 10)
{
insertionSort(arrayPointer, last + 1);
}

else
{
// Partitioning Step
while (firstTemp <= lastTemp)
{
while (arrayPointer[firstTemp] < pivot)
firstTemp++;

while (arrayPointer[lastTemp] > pivot)
lastTemp--;

if (firstTemp <= lastTemp)
{
temp = arrayPointer[firstTemp];
arrayPointer[firstTemp] = arrayPointer[lastTemp];
arrayPointer[lastTemp] = temp;
firstTemp++;
lastTemp--;
}
}

// Recursive step
if (first < lastTemp)
modifiedQuickSort(arrayPointer, first, lastTemp);

if (firstTemp < last)
modifiedQuickSort(arrayPointer, firstTemp, last);
}
}

void insertionSort(arrPtr &arrayPointer, const int &arraySize)
{
int i, key, j;

for (i = 1; i < arraySize; i++)
{
key = arrayPointer[i];

j = i-1;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arrayPointer[j] > key)
{
arrayPointer[j+1] = arrayPointer[j];
j = j-1;
}
arrayPointer[j+1] = key;
}
}

Answer

If you inspect the execution of the insertion sort you see that it gets to sort far larger arrays than size 10. This would have been caught, had you followed the excellent advice given in Lipperts writeup linked by πάντα ῥεῖ.

If you’ve still got a bug then first double check that your specifications contain all the preconditions and postconditions of every method.

and

If you’ve still got a bug then learn how to write assertions that verify your preconditions and postconditions.

The function call

if((last - first) < 10)
{
    insertionSort(arrayPointer, last + 1);
}

Indicates that insertionSort operates on the entire array [0, last] not [first, last].

Change this and the performance of your modifiedQuicksort will behave as expected.