C/C++

В чем ошибка в реализации быстрой сортировки? И как изменить, чтобы все стало ок?

void quickSort(vector<int> &a_, int i, int j){
if(i >= j)
return;
pair<int, int> pivot = {a_[(i + j) / 2], (i + j) / 2};
for(int k = i; k <= j; k++){
if(a_[k] < pivot.first && k > pivot.second){
swap(a_[k], a_[pivot.second]);
pivot.second = k;
}
if(a_[k] > pivot.first && k < pivot.second){
swap(a_[k], a_[pivot.second]);
pivot.second = k;
}
}
quickSort(a_, i, pivot.second);
quickSort(a_, pivot.second + 1, j);
}

при тесткейсе: a = {12, 7, 92, 5, 18, 4, 32, 48, 11, 74}
вместо: 4 5 7 11 12 18 32 48 74 92
выводит: 4 5 7 11 12 18 32 48 92 74
ЛГ
Леонид Гонтаренко
95
ХЗ, быструю сортировку пока без промлем умею реализовывать только на JS и Python
a = [5,4,8,7,3,4]
[4,3,4][5][8,7]
a = [4,3,4,5,8,7]
[4,3,4][5][8,7]
[[3][4,4][] [5] [[7][8][]]
Айдын Байыс
Айдын Байыс
75 467
Лучший ответ
ошибка не техническая, а логическая:

смотри, например, обрабатываем массив
8 5 4 6 3 7 2 1
выбираем средний элемент в качестве опорного: 6

сравниваем с опорным элемент на 0-й позиции: 8 > 6, меняем:
>6* 5 4 8* 3 7 2 1
пока всё хорошо, все элементы слева от опорного - меньше шестёрки

сравниваем с опорным элемент на 1-й позиции: 5 < 6, меняем:
5* >6* 4 8 3 7 2 1
пока всё хорошо, все элементы слева от опорного - меньше шестёрки

сравниваем с опорным элемент на 2-й позиции: 4 < 6, меняем:
5 4* >6* 8 3 7 2 1
пока всё хорошо, все элементы слева от опорного - меньше шестёрки

сравниваем с опорным элемент на 3-й позиции: 8 > 6, оставляем:
5 4 6* >8* 3 7 2 1
пока всё хорошо, все элементы слева от опорного - меньше шестёрки

сравниваем с опорным элемент на 4-й позиции: 3 < 6, меняем:
5 4 3* 8 >6* 7 2 1
и тут восьмёрка оказывается слева от опорного элемента!

продолжаем этап, и в результате получаем неправильно раскиданный массив:
5 4 3 8 2 7 1 6
Владимир Парафилов
Владимир Парафилов
90 714

Похожие вопросы