Быстрая сортировка Hoare в c - PullRequest
Новая
       10

Быстрая сортировка Hoare в c

0 голосов
/ 11 февраля 2020

Аналогично другим пользователям я использую этот алгоритм Википедии. Однако я попытался переопределить алгоритм, используя арифметику указателей c. Однако мне трудно найти, где я ошибся.

Я думаю, что это, если утверждение, вероятно, является причиной, но я не уверен. 

...  
if (left >= right) {  
ret = (right - ptr);  
return ret;  
}  
temp = *left;
*left = *right;
*right = temp;

/* sortstuff.h */

extern void quicksort(const size_t n, int * ptr);

/* sortstuff.c */ 
size_t quicksortpartition(const size_t n, int * ptr);

void quicksort(const size_t n, int * ptr) {
    int* end = ptr + n - 1;

    // for debug purposes
    if (original_ptr == NULL) {
        original_ptr = ptr;
        original_count = n;
    }

    if (n > 1) {
        size_t index = quicksortpartition(n, ptr);
        quicksort(index, ptr);
        quicksort(n - index - 1, ptr + index + 1);
    }
    return;
}

size_t quicksortpartition(const size_t n, int * ptr) {
    int* right = ptr + n - 1;
    int* pivot = ptr + (n - 1) / 2;
    int* left = ptr;
    int temp;
    size_t ret = NULL;

    while (1) {
        while (*left <= *pivot && left < pivot) {
            ++left;
        }
        while (*right > *pivot) {
            --right;
        }
        if (left >= right) {
            ret = (right - ptr);
            return ret;
        }
        temp = *left;
        *left = *right;
        *right = temp;
        //print_arr();
    }
}

int main(void) {

}

/* main.c */ 

int array0[] = {5, 22, 16, 3, 1, 14, 9, 5};
const size_t array0_count = sizeof(array0) / sizeof(array0[0]);

int main(void) {
    quicksort(array0_count, array0);

    printf("array out: ");
    for (size_t i = 0; i != array0_count; ++i) {
        printf("%d ", array0[i]);
    }
    puts("");
}

Я не думаю, что есть какие-то ошибки по одной

Ответы [ 2 ]

0 голосов
/ 11 февраля 2020

Pivot должен быть int, а не указателем. Кроме того, чтобы более точно следовать алгоритму Wiki, параметрами должны быть два указателя, а не счетчик и указатель. Я переместил логи раздела c в функцию быстрой сортировки. 

void QuickSort(int *lo, int *hi)
{
int *i, *j;
int p, t;
    if(lo >= hi)
        return;
    p = *(lo + (hi-lo)/2);
    i = lo - 1;
    j = hi + 1;
    while (1){
        while (*(++i) < p);
        while (*(--j) > p);
            if (i >= j)
                break;
            t = *i;
            *i = *j;
            *j = t;
    }
    QuickSort(lo, j);
    QuickSort(j+1, hi);
}

Вызов будет: 

    QuickSort(array0, array0+array0_count-1);
0 голосов
/ 11 февраля 2020

Код, который вы представили, не совсем точно реализует алгоритм, на который вы ссылались. Рассмотрим, в частности, этот l oop: 

        while (*left <= *pivot && left < pivot) {
            ++left;
        }

Соответствующий l oop в описании алгоритма не имеет аналога критерия выхода left < pivot l oop, и его аналог *left <= *pivot использует строго меньше, чем (<), а не (<=).

Легко видеть, что прежнее несоответствие должно представлять собой ошибку реализации. Конечная отсортированная позиция точки поворота - это место, где встречаются левый и правый указатели, но это условие не позволяет левому указателю когда-либо продвигаться дальше начальной позиции точки поворота. Таким образом, если правильная позиция находится справа от начальной позиции, то функция разделения, безусловно, не может вернуть правильное значение. Требуется более вдумчивый анализ, чтобы понять, что на самом деле функция разбиения, кроме того, склонна к бесконечному циклу в этом случае, хотя я думаю, что это несколько зависит от данных.

Последнее расхождение представляет собой временную ошибку. Это может привести к переполнению конца массива в случае, если выбранное значение поворота окажется самым большим значением в массиве, но это частично основано на том факте, что условие left < pivot является ошибочным и должно быть удалено. Вы могли бы заменить последнее на left < right, чтобы решить эту проблему, но, хотя вы могли бы сформировать рабочую сортировку таким образом, это, вероятно, не улучшило бы детали логики c, представленные в описании алгоритма.

Обратите внимание, однако, что с вариацией <= либо quicksortpartition() необходимо выполнить дополнительную работу (в настоящее время не предусмотрено), чтобы гарантировать, что значение поворота заканчивается в вычисленной позиции поворота, либо для функции quicksort требуется отказаться от своего предположения, что это произойдет. Первый более практичен, если вы хотите, чтобы ваш сорт был устойчивым.

...