Быстрая сортировка с вставкой сортировки

Question

Я работал над этим кодом несколько часов. Целью является написание оптимизированной быстрой сортировки (с сортировкой вставками) на массиве указателей (которые указывают на объекты, которые можно сравнивать). Сортировка вставок должна использоваться с размерами массива <4. </p>

Пока у меня работает сортировка вставки, когда я передаю массив <4. </p>

Предполагается, что быстрая сортировка использует средний индекс в качестве точки поворота и перемещает все <ось поворота влево от точки поворота и все> ось поворота вправо от точки поворота.

Я даже не уверен, что мой общий подход к быстрой сортировке правильный. Это моя первая попытка написать быструю сортировку. Я мог бы действительно использовать толчок в правильном направлении здесь. Закомментированный код - это то, что я уже пробовал.

Если что-то неясно, дайте мне знать. Спасибо за помощь!

void quickSort(Comparable ** array, int fromIndex, int toIndex)
{
    while (fromIndex < toIndex)
    {
        if ((toIndex - fromIndex +1 ) < 4)
        {
            insertionSort(array, fromIndex, toIndex);
            break;
        }
        else
        {
            int pivotIndex = partition(array, fromIndex, toIndex);
            quickSort(array, fromIndex, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, toIndex);
        }
    }
}
int partition(Comparable ** array, int fromIndex, int toIndex)
{
    //Comparable *front = array[fromIndex+1];
    int midIndex = (toIndex + fromIndex) / 2;
    //int frontIndex = fromIndex;
    //Comparable *back = array[toIndex - 1];
    //int backIndex = toIndex - 1;
    //Comparable *compare = front;
    //int compareIndex = frontIndex;

    SortFirstMiddleLast(array, fromIndex, midIndex, toIndex);
    swap(array, midIndex, toIndex - 1);
    int pivotIndex = toIndex - 1;
    Comparable * pivot = array[pivotIndex];
    int indexLeft = fromIndex + 1;
    int indexRight = toIndex - 2;

    bool sortFinished = false;
        while (*array[indexLeft] < *pivot)
        {
            indexLeft++;
        }
        while (*array[indexRight] > *pivot)
        {
            indexRight--;
        }
        if ((*array[indexLeft] >= *pivot) && (*array[indexRight] <= *pivot))
        {
            if (indexLeft < indexRight)
            {
                swap(array, indexLeft, indexRight);
                indexLeft++;
                indexRight--;
                sortFinished = true;
            }
        }
            if (sortFinished == true)
            {
                swap(array, pivotIndex, indexLeft);
                pivotIndex = indexLeft;
                return pivotIndex;
            }

//  ++frontIndex; // advance to next element
//  while (*array[frontIndex] < *array[backIndex])
//  {
//      // search forward for out of order element
//      while ((*array[frontIndex] < *array[backIndex]) && (*array[fromIndex] > *array[frontIndex]))
//          ++frontIndex;
//      //search backward for out of order element
//      while ((*array[frontIndex] < *array[backIndex]) && (*array[compareIndex] <= *array[backIndex]))
//          --backIndex;
//      swap(array, frontIndex, backIndex);
//  }
//  //insert mid position comparison element
//  if (*array[compareIndex] >= *array[frontIndex])
//  {
//      swap(array, fromIndex, frontIndex);
//      returnValue = frontIndex;
//  }
//  else
//  {
//      swap(array,fromIndex, (frontIndex - 1));
//      returnValue = (frontIndex - 1);
//  }
//  return returnValue;
}
void swap(Comparable ** array, int swapIndex1, int swapIndex2)
{
    Comparable * temp = array[swapIndex1];
    array[swapIndex1] = array[swapIndex2];
    array[swapIndex2] = temp;
}

void SortFirstMiddleLast(Comparable ** array, int fromIndex, int midIndex, int toIndex)
{ 
    // first must be less than mid, must be less than last
    if (*array[fromIndex] > *array[midIndex])
    {
        swap(array, fromIndex, midIndex);
    }
    if (*array[fromIndex] > *array[toIndex - 1])
    {
        swap(array, fromIndex, toIndex - 1);
    }
    if (*array[midIndex] > *array[toIndex - 1])
    {
        swap(array, midIndex, toIndex - 1);
    }
}
void insertionSort(Comparable ** array, int fromIndex, int toIndex)
{
    for (unsigned i = fromIndex + 1; i < toIndex; i++)
    {
        for (unsigned j = i; j > 0; j--)
        {
            if (*array[j] < *array[j - 1])
            {
                swap(array, j, j-1);
            }
            else
                break;
        }
    }
}