ошибка быстрой сортировки не найдена

Question

после целого дня работы над этим, я не могу найти, что не так с моим кодом, я не могу найти, где моя ошибка.Может кто-нибудь, пожалуйста, помогите мне понять, что я сделал не так?

void a_quick(int array[], int i, int j){
    //Array Quick Sort
    if ((j - i) < 2){
        return;
    }
    int top = j;
    int bot = i;
    int p_location = i + (j + i) / 2;
    int pivot = array[p_location];
    while (i < j){
        while (array[i] < pivot){
            i++;
        }
        while (array[j] > pivot){
            j--;
        }
        if (i <= j){
            swap(array[i], array[j]);
            i++;
            j--;
        }
    }
    a_quick(array, bot, p_location);
    a_quick(array, p_location + 1, top);

}

запуск кода на массивах 64k int приведет к сбою компьютера, и мне нужно, чтобы он работал на 128k.

я получаю:

Test Array:
703 322 673 141 253 547 662 37 723 529 316 190 288 40 264 446 890 370 6 393

Quick Sort w Array:
6 37 40 141 253 190 316 288 264 322 393 370 446 529 723 662 890 547 673 703

Answer 1

у меня этот код отлично работает

   void a_quick(int array[], int i, int j){
    //Array Quick Sort

    int top = j;
    int bot = i;
    int p_location = (j + i) / 2;
    int pivot = array[p_location];
    do {
        while (array[i] < pivot)i++;
        while (array[j] > pivot)j--;
        if (i <= j){
            swap(array[i], array[j]);
            i++;
            j--;
        }
    } while (i<=j);
    if (bot<j) a_quick(array, bot, j);// problem is most likely here
    if (i<top) a_quick(array, i, top);// or here
}

Answer 2

это должно работать

void a_quick(int array[], int i, int j){
//Array Quick Sort
if (j <= i) return; // change here (j - i) < 1 (not 2)

int top = j;
int bot = i;
int p_location = (j + i) / 2; // change here - by + so you pick the middle
int pivot = array[p_location];
while (i < j){
    while (array[i] < pivot){
        i++;
    }
    while (array[j] > pivot){
        j--;
    }
    if (i <= j){
        swap(array[i], array[j]);
        i++;
        j--;
    }
}
a_quick(array, bot, j); // change here (dont use p_loc, use i and j)
a_quick(array, i, top); // and here

}

Answer 3

В способе, которым вы вычисляете пивот, есть проблема. Спросите себя, что происходит, когда индексы 5 и 9. Вместо этого:

p_location = (j - i) / 2;

Попробуйте что-то вроде:

p_location = i + (j - i) / 2;

Answer 4

Это довольно сломано.Вам необходимо переместить элемент сводки в сторону (условно к началу массива, который вы разбиваете), поскольку очень маловероятно, что половина элементов будет меньше, чем половина, а половина больше.

И как другиесказал, что вы включаете сводку в обоих подразделах, когда вы рекурсивномассив теперь так, как и следовало ожидать)

Answer 5

Одна проблема состоит в том, что последние две строки должны иметь следующий вид:

a_quick(array, bot, p_location - 1);
a_quick(array, p_location + 1, top);

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

Для сравнения взгляните на несколько версий псевдокода, доступных в Wikipedia .

Answer 6

Это должно работать

#include <memory>
#include <iterator>
#include <algorithm>
#include <iostream>

void a_quick(int array[], int i, int j){
    //Array Quick Sort
    if ((j - i) < 2){
        return;
    }
    int top = j;
    int bot = i;

    // Bug 1: Pick something in the correct range.
    int pivot = array[i + (j-i)/2];
    while (i < j){
        while (array[i] < pivot){
            i++;
        }
        while (array[j] > pivot){
            j--;
        }
        if (i < j)
        {
            // Bug 2: swap is in the std namespace
            std::swap(array[i], array[j]);

            // Bug 3: Don't increment the pointers.
            //        What if you hit the pivot point.
        }
    }
    // The split is not at where you selected the pivot point.
    // As that could be any number and it may not split evenly.
    // So you pick either of i or j. I picked j as the mid point
    // One sort upto j the other sorts from j+1 to the end.
    a_quick(array, bot, j );
    a_quick(array, j+1 , top );
}


int main()
{
    int d[] = { 703, 322, 673, 141, 253, 547, 662, 37, 723, 529, 316, 190, 288, 40, 264, 446, 890, 370, 6, 393 };
    int size = sizeof(d)/sizeof(d[0]);

    a_quick(d, 0, size - 1 );

    std::copy(d, d+size, std::ostream_iterator<int>(std::cout, ", "));
}

Answer 7

Я пытался:

void a_quick(int array[], int i, int j){
    //Array Quick Sort
    if ((j - i) < 2){
        return;
    }
    int top = j;
    int bot = i;
    int p_location = (j - i) / 2;
    int pivot = array[p_location];
    while (i < j){
        while (array[i] < pivot){
            i++;
        }
        while (array[j] > pivot){
            j--;
        }
        if (i <= j){
            std::swap(array[i], array[j]);
            i++;
            j--;
        }
    }
    a_quick(array, bot, p_location);// problem is most likely here
    a_quick(array, p_location, top - 1);// or here
}

int main()
{
    // int d[] = { 5, 1, 6, 4, 8, 2, 3, 7, 9, 0};
    int d[] = { 5, 1, 6, 4, 8, 2, 3, 7, 0, 9};
    a_quick(d, 0, 9);

    std::copy(d, d+10, std::ostream_iterator<int>(std::cout));
}

> g++ sort.cpp
> ./a.exe
0124356789 >

И все работало нормально.
То, что нам действительно нужно, это пример того, как это не удалось.

Надеюсь, с полным комплектом тестов, который просто компилируется и запускается и показывает ошибку.