Итак, я сегодня немного поспорил с моим профессором CS о том, подходит ли функция разбиения, которая является частью моего алгоритма быстрой сортировки, как раздел Хоара. По ее словам, существует только один конкретный способ реализации раздела Hoare, а все остальное неправильно.
Это заставило меня задуматься: действительно ли существует конкретное определение раздела Hoare? Я всегда предполагал, что разбиение Hoare — это любой алгоритм разбиения, который сортируется с использованием метода, разработанного Тони Хоаром (то есть два итератора, пересекающие список в противоположных направлениях); я не думал, что точная реализация алгоритма действительно имеет значение. Это правильно, или действительно есть только один «правильный» способ реализовать алгоритм Хоара.
Вот мой алгоритм разбиения:
template <typename T>
int partArray(T* array, int leftIndex, int rightIndex)
{
int pivot = leftIndex, middle = (leftIndex + rightIndex) / 2, leftIterator = leftIndex + 1, rightIterator = rightIndex;
//Move median element into pivot position
if (array[leftIndex] > array[rightIndex])
SWAP(array[leftIndex], array[rightIndex]);
if (array[middle] > array[rightIndex])
SWAP(array[middle], array[rightIndex]);
if (array[middle] > array[leftIndex])
SWAP(array[middle], array[leftIndex]);
//Partition array using Hoare's algorithm
while (true)
{
while (array[leftIterator] <= array[pivot] && leftIterator < rightIndex) leftIterator++;
while (array[rightIterator] >= array[pivot] && rightIterator > leftIndex) rightIterator--;
if (leftIterator < rightIterator)
SWAP(array[leftIterator], array[rightIterator]);
else
break;
}
SWAP(array[pivot], array[rightIterator]);
//Return final position of pivot
return rightIterator;
}
Задача ещё не решена.