Почему этот QuickSort работает?

Question

Я считаю, что этот подход к быстрому сортированию сбивает с толку и ошибочен, но, похоже, он работает. Я имею в виду this pseudocode. Примечание: у них также есть реализация C в конце статьи, но она сильно отличается от их псевдокода, поэтому меня это не волнует.

Я также написал в C, как это, пытаясь остаться верным псевдокоде как можно больше, даже если это означает, что делает некоторые странные C вещи:

#include <stdio.h> 

int partition(int a[], int p, int r) 
{ 
    int x = a[p]; 

    int i = p - 1; 
    int j = r + 1; 

    while (1) 
    { 
     do 
      j = j - 1; 
     while (!(a[j] <= x)); 

     do 
      i = i + 1; 
     while (!(a[i] >= x)); 

     if (i < j) 
     { 
      int t = a[i]; 
      a[i] = a[j]; 
      a[j] = t; 
     } 
     else 
     { 
      for (i = 1; i <= a[0]; ++i) 
       printf("%d ", a[i]); 
      printf("- %d\n", j); 

      return j; 
     } 
    } 
} 


int main() 
{ 
    int a[100] = //{8, 6,10,13,15,8,3,2,12}; 
       {7, 7, 6, 2, 3, 8, 4, 1}; 

    partition(a, 1, a[0]); 
    return 0; 
} 

Если запустить это, вы» будете получать следующий вывод:

1 6 2 3 4 8 7 - 5

Однако, это не так, не так ли? Ясно, что a[5] не имеет всех значений, прежде чем он окажется ниже, так как a[2] = 6 > a[5] = 4. Не говоря уже о том, что 7 должен быть стержнем (начальный a[p]), и все же его позиция неверна и потеряна.

следующий алгоритм раздела берется из wikipedia:

int partition2(int a[], int p, int r) 
{ 
    int x = a[r]; 
    int store = p; 

    for (int i = p; i < r; ++i) 
    { 
     if (a[i] <= x) 
     { 
      int t = a[i]; 
      a[i] = a[store]; 
      a[store] = t; 

      ++store; 
     } 
    } 

    int t = a[r]; 
    a[r] = a[store]; 
    a[store] = t; 

    for (int i = 1; i <= a[0]; ++i) 
     printf("%d ", a[i]); 
    printf("- %d\n", store); 

    return store; 
} 

И производит этот выход:

1 6 2 3 8 4 7 - 1

, который является правильным по моему мнению: ось (a[r] = a[7]) достигла своего окончательного положения.

Однако, если использовать исходную функцию секционирования в следующем алгоритме:

void Quicksort(int a[], int p, int r) 
{ 
    if (p < r) 
    { 
     int q = partition(a, p, r); // initial partitioning function 

     Quicksort(a, p, q); 
     Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r. 
    } 
} 

... это, кажется, правильный алгоритм сортировки. Я проверил его на множестве случайных входов, включая все массивы 0-1 длины 20.

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

Так что мои вопросы:

1. Может кто-нибудь опубликовать пример, на котором алгоритм не работает?
2. Если нет, то почему это работает, поскольку часть раздела кажется неправильной? Это еще один подход к разделению, о котором я не знаю?

Answer 1

Я думаю, что разбиение правильное. 7 - стержень. Исходный массив разбивается на вспомогательный массив длиной 5, содержащий элементы, меньшие или равные 7, и вспомогательный массив длиной 2, содержащий элементы, большие или равные 7.

Answer 2

От Wikipedia (я подчеркивал ту часть, которую я думаю, адреса вашего вопроса непосредственно):

Это разбиение алгоритма на месте. Это разделяет часть массива между индексами слева и справа , включительно, путем перемещения всех элементов меньше или равно массива [] pivotIndex к началу подмассива, в результате чего все больше элементов следующих их. В процессе он также находит конечное положение для элемента поворота, который возвращается . Он временно перемещает элемент поворота в конец подмассива , так что он не попадает в . Поскольку он использует только обмены , последний список имеет то же самое элементов в качестве исходного списка. Извещение , что элемент может быть обменен несколько раз, прежде чем он достигнет своего окончательного места. Также следует отметить , что в случае сводных дубликатов в входной массив они могут быть распределены через левый подрамник, возможно, в случайный порядок. Это не представляет собой ошибку разбиения на разделы , поскольку последующая сортировка будет изменена и, наконец, «склеить» их вместе.

Возможно, это было то, что вам не хватало?

Answer 3

Вы путаться между индексом элемента и ITEN значением

Посмотрите на свой заголовке

int partition(int a[], int p, int r) ; 

Теперь, если мы изменили тип данных на массиве в некоторых странных типа данных, вам будет видеть проблему

int partition(Otherdatatype a[], int p, int r) ; 

Вы вызываете функцию из ваших основных с

partition(a, 1, a[0]); 

См. Проблему a [0] - значение записи в [0], а не значение индекса.

Предположите, что значение [0] имеет значение 200 в вашем коде, просто измените значение первого элемента на 200, и вы получите ошибку времени выполнения «попытка получить доступ к памяти вне диапазона», потому что если вы следуете за через [0] = 200, который передается в раздел как значение r, затем следует за тем, что происходит внутри раздела.

Следует помнить, что это подпрограмма сортировки в заголовке раздела. Список в массиве a может быть не того же типа, что и индексы. P и r вашего заголовка явно индексы, относящиеся к позиции индекса и a - список, который нужно отсортировать.

Таким образом, ваш главный старт рода является

partition(a, 0, items_in_array-1); 

Видят, почему? Массив a работает от [0] ...а [items_in_array-1]

Так что в вашем образце выше вы предварительно загрузили 8 значений в массиве таким образом ваш раздел вызова от основной должна быть

partition(a, 0, 7); 

Answer 4

Расширение на сверху вот что он должен выглядеть

void swap(int *a, int *b) 
{ 
    int x; 

    x = *a; 
    *a = *b; 
    *b = x; 
} 

int partition(int s[], int l, int h) 
{ 
    int i; 
    int p;/* pivot element index */ 
    int firsthigh;/* divider position for pivot element */ 

    p = h; 
    firsthigh = l; 
    for (i = l; i < h; i++) 
     if(s[i] < s[p]) { 
      swap(&s[i], &s[firsthigh]); 
      firsthigh++; 
     } 
    swap(&s[p], &s[firsthigh]); 

    return(firsthigh); 
} 

void quicksort(int s[], int l, int h) 
{ 
    int p;/* index of partition */ 
    if ((h - l) > 0) { 
     p = partition(s, l, h); 
     quicksort(s, l, p - 1); 
     quicksort(s, p + 1, h); 
    } 
} 

int main()  
{   
    int a[100] = //{8, 6,10,13,15,8,3,2,12}; 
        {7, 7, 6, 2, 3, 8, 4, 1};    
    quicksort(a, 0, 7); 
    return 0; 
}