Проблема с реализацией QuickSort с C ++

Question

Таким образом, ответ оказался частично правильным для этого простого кода.Результат: «1 1 2 3 4 4 2 6 8 5» Я думаю, что проблема должна быть связана с рекурсией и разбиением.Где я не так сделал ??

#include <iostream>

using namespace std;


void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high){
    int i = low - 1;
    int pivot = num[high];
    for(int j = low; j <= high -1; j++){
        if(num[j] <= pivot){
            i++;
            swap(&num[i], &num[j]);
        }
        else{
            continue;
        }
    swap(&num[i+1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i+2, high);
    }
}

int main(){
    int test[] = {3,1,2,6,5,4,8,1,2,4};
    quick_sort(test, 0, sizeof(test)/sizeof(test[0])-1);
    for(int i = 0; i < sizeof(test)/sizeof(test[0]); ++i){
        cout << test[i] << endl;
    }
    return 0;

}

Answer 1

Как указывал @Loc Tran, ваш сводный своп и последующие левые и правые быстрые сортировки должны быть вне цикла.Нет необходимости else continue;.Целью цикла for является поиск позиции (i) для нашего элемента pivot, чтобы все элементы слева были меньше pivot, а справа больше pivot.

Как только позиция (i+1) определена, поместите ось туда, поменяв местами, и затем выполните быструю сортировку по левой и правой сторонам pivot.

Также быструю сортировку следует выполнять только тогда, когда low < high.

#include <iostream>

using namespace std;


void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high){
    if(low >= high)
        return;
    int i = low - 1;
    int pivot = num[high];
    for(int j = low; j <= high -1; j++){
        if(num[j] <= pivot){
            i++;
            swap(&num[i], &num[j]);
        }
    }
    swap(&num[i+1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i+2, high);
}

int main(){
    int test[] = {3,1,2,6,5,4,8,1,2,4};
    quick_sort(test, 0, sizeof(test)/sizeof(test[0])-1);
    for(int i = 0; i < sizeof(test)/sizeof(test[0]); ++i){
        cout << test[i] << endl;
    }
    return 0;

}

Answer 2

Ваша проблема в цикле for.Значение i должно обновляться после завершения цикла for, а затем использовать значение i для вызовов swap и других вызовов quick_sort.Но ваш исходный код я обновил внутри цикла for и использовал его для вызовов swap и других быстрых сортировок.Это проблема.Вот мое решение:

#include <iostream>

using namespace std;


void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high) {
    if (low >= high) return;
    int i = low - 1;
    int pivot = num[high];
    for (int j = low; j <= high - 1; j++) {
        if (num[j] <= pivot) {
            i++;
            swap(&num[i], &num[j]);
        }
        else {
            continue;
        }
    } // move to correct line
    swap(&num[i + 1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i + 2, high);
    // } this line should be moved to another line
}

int main() {
    int test[] = { 3,1,2,6,5,4,8,1,2,4 };
    quick_sort(test, 0, sizeof(test) / sizeof(test[0]) - 1);
    for (int i = 0; i < sizeof(test) / sizeof(test[0]); ++i) {
        cout << test[i] << endl;
    }
    return 0;

}