Ищет ошибку в C++ Quicksort/Insertion sort combo

Question

Я пытаюсь создать комбайну сортировки quicksort/insertion, как говорят некоторые ее довольно быстро, поскольку она решает большие подмассивы с быстрой сортировкой и меньшими массивами с сортировкой вставки, но что-то определенно не правильно. Я тестировал сортировку с некоторыми файлами, которые я сгенерировал. В настоящее время я использую файл из 1 000 000 номеров, при этом предел диапазона для каждого номера составляет от 1 до 1 000 000. До добавления сортировки вставки я смог сортировать 1 миллион номеров примерно через 0,2 секунды после добавления сортировки вставки в качестве условного оператора if, мне повезло сортировать 100 000 номеров менее чем за 4 секунды, поэтому я знаю, что есть ошибка в коде, но я не могу ее найти. Мой код - всего лишь амальгама различных онлайн-ссылок для этих типов методов сортировки. Я не претендую на то, что этот код является моим собственным, и при необходимости может предоставить ссылки на оригинал. Однако ссылки, которые я использовал, не были написаны на C++ и были ориентированы на классы, поэтому мне пришлось внести изменения, поэтому я думаю, что есть ошибка.

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 1

Если вы проверяете выполнение вставки рода вы видите, что он получает рода гораздо большие массивы, чем размер 10. Это был бы пойман, если бы вы следили за отличные советы, приведенные в Lipperts writeup связаны πάντα ῥεῖ.

Если у вас все еще есть ошибка, сначала проверьте, что ваши спецификации содержат все предварительные условия и постусловия каждого метода.

и

Если у вас еще есть ошибка, то научиться писать утверждения, которые проверяют свои предпосылки и постусловия.

Функция вызова

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

Указывает, что insertionSort работает на весь массив [0, last] не [first, last].

Изменить это, и производительность вашего modifiedQuicksort будет вести себя так, как ожидалось.