Раздел быстрой сортировки не работает для нечетного ввода
Я пытаюсь внедрить быструю сортировку самостоятельно, в соответствии с введением Кормена в алгоритмы. У меня есть следующий код, но также проблема с ним:
void quickSort(Node* left, Node* right) {
Node* start = left;
Node* cur = left->next;
if (left == right) return;
while (cur != right) {
if (start->data < cur->data) swap(start->data,cur->data);
cur = cur->next;
}
swap(left->data,cur->data);
Node* oldCur = cur;
cur = getPrevious(cur);
if (cur != nullptr && (getPrevious(left) != cur) && (cur->next != left)) quickSort(left,cur);
cur = oldCur->next;
if (cur != nullptr && (getPrevious(cur) != right) && (right->next != cur)) quickSort(cur, right);
}
Для ровной длины это работает правильно
7 6 5 8 4 3 2 1
1 2 3 4 5 6 7 8
но для нечетного числа входных данных вывод выглядит следующим образом
7 6 5 8 4 2 1
1 2 5 4 6 7 8
Я предполагаю, что где-то в части раздела алгоритма есть проблема, но я не смог ее найти.
РЕДАКТИРОВАТЬ
Я, наверное, нашел проблему и немного изменил алгоритм. Прямо сейчас я не могу найти какой-либо контрпример для этого, но если кто-то видит что-то не так, пожалуйста, укажите это:-)
void quickSort(Node* left, Node* right) {
Node* start = left;
Node* cur = left;
T pivot = start->data;
if (left == right) return;
if (left->next == right) {
if (right->data < left->data) swap(left->data,right->data);
return;
}
swap(start->data,right->data);
while (cur != right->next) {
if (cur->data < pivot) {
swap(cur->data,start->data);
start = start->next;
}
cur = cur->next;
}
swap(right->data,start->data);
quickSort(left, start);
if (start->next != nullptr) quickSort(start->next, right);
}