Реализация быстрой сортировки C++

154

25 мая 2022, 03:10

Пытаюсь реализовать алгоритм быстрой сортировки, но что-то идет не так. Вроде пишу прямо по книге (Кормен), но алгоритм работает некорректно и медленно. Кажется, я упускаю что-то очень важное, помогите разобраться, пожалуйста. Прикрепляю код.

int* Partition(int* p, int* r) {
    int x = *r;
    int* i = p - 1;
    for (int* j = p; j < (r - 1); j++) {
        if (*j <= x) {
            std::swap(*i, *j);
        }
    }
    std::swap(*(i+1), *r);
    return i + 1;
}
void QuickSort(int* p, int* r) {
    if (p < r) {
        int* q = Partition(p, r);
        QuickSort(p, q - 1);
        QuickSort(q + 1, r);
    }
}

Функция Partition принимает два указателя - на начало и конец массива. В функции фиксируется опорный элемент (х). В массиве происходит перестановка элементов таким образом, что в правой части находятся все элементы, которые меньше опорного, а в левой - больше. Функция возвращает указатель на опорный элемент. Затем вызывается рекурсивная функция QuickSort, которая должна сортировать массив.

Answer 1

ошибки :

int* Partition(int* p, int* r) {
    int x = *r;
    // начальный элемент i выходит за пределы массива
    int* i = p - 1;
    // цикл проходит до r-2 , это очень мало
    for (int* j = p; j < (r - 1); j++) {
        // вы переставляете элементы ,что меньше в начало
        // если нужно будет наоборот, поменяете условие на >=
        if (*j <= x) {
            std::swap(*i, *j);
           
            // здесь надо ещё изменить метку i
        }
    }
    // элементы меньше имеют индекс i
    std::swap(*(i+1), *r);
    return i + 1;
}

исправляем :

int* Partition(int* p, int* r) {
    int x = *r;
    // начальный элемент i указывает на первый
    int* i = p ;
    // цикл проходим до r-1
    for (int* j = p; j < r ; j++) {
        if (*j <= x) {
            std::swap(*i, *j);
            
            // потому-что этот элемент уже меньше опорного
            ++ i ;
        }
    }
    // правим элемент i 
    std::swap(*i, *r);
    return i ;
}