Раздел QuickSort и Hoare

Ответ 1

Чтобы ответить на вопрос "Почему работает разделение Хоар?":

Давайте упростить значения в массиве только три вида: значения L (те, меньше, чем значение поворота), значения E (те, равно значению поворота), и значение G (те, больше, чем значение поворота).

Мы также укажем специальное имя в одном месте в массиве; мы назовем это местоположение s, и это место, где находится указатель j, когда процедура заканчивается. Знаем ли мы заранее, какое место находится? Нет, но мы знаем, что какое-то место встретит это описание.

С помощью этих терминов мы можем выразить цель процедуры разбиения в несколько разных терминах: она состоит в том, чтобы разбить один массив на два меньших подматрицы, которые не сортируются по-разному друг относительно друга. Это требование не "неправильно отсортировано" выполняется, если выполняются следующие условия:

• Под-массив "низкий", который идет от левого конца массива до и включает s, не содержит значений G.
• Под-массив "высокий", который начинается сразу после s и продолжается до правого конца, не содержит значений L.

Это действительно все, что нам нужно сделать. Нам даже не нужно беспокоиться, где значения E заканчиваются на любом проходе. До тех пор, пока каждый проход получает субмассивы по отношению друг к другу, последующие проходы будут заботиться о любом беспорядке, который существует внутри любого подматрица.

Итак, теперь давайте обратимся к вопросу с другой стороны: как процедура секционирования гарантирует отсутствие значений G в s или слева от нее, а L значений справа от s?

Ну, "набор значений справа от s" совпадает с "набором ячеек, который j-указатель перемещается, прежде чем он достигнет s". И "набор значений слева и в том числе s" совпадает с "набором значений, которые i-указатель перемещает, прежде чем j достигает s".

Это означает, что любые значения, которые неуместны, будут на некоторой итерации цикла быть под одним из двух наших указателей. (Для удобства, скажем, это j-указатель, указывающий на значение L, хотя он работает точно так же для i-го указателя, указывающего на значение G.) Где будет указатель i, когда j-указатель находится на неуместном значении? Мы знаем, что это будет:

• в местоположении в "низком" подмассиве, где значение L может идти без проблем;
• указывая на значение, которое либо E, либо значение G, которое может легко заменить значение L под j-указателем. (Если бы это не было на значении E или G, оно не остановилось бы там.)

Обратите внимание, что иногда указатели я и j фактически останавливаются на значениях E. Когда это произойдет, значения будут переключаться, даже если в этом нет необходимости. Это не наносит вреда; мы уже говорили, что размещение значений E не может вызвать неправильную сортировку между субмассивами.

Итак, суммируя, разбиение Хоар работает, потому что:

• Он разделяет массив на более мелкие под-массивы, которые не сортируются некорректно относительно друг друга;
• Если вы продолжаете делать это и рекурсивно сортируете суб-массивы, в конечном итоге не останется ничего от несортированного массива.

Ответ 2

Я считаю, что с этим кодом есть две проблемы. Для начала, в вашей функции Quicksort, я думаю, вы хотите изменить порядок строк

 int q=HoarePartition(a,start,end);
 if (end<=start) return;

чтобы они были такими:

 if (end<=start) return;
 int q=HoarePartition(a,start,end);

Однако вы должны сделать еще больше, чем это; в частности, это должно читать

 if (end - start < 2) return;
 int q=HoarePartition(a,start,end);

Причиной этого является то, что раздел Hoare не работает корректно, если диапазон, который вы пытаетесь разбить, имеет нулевой размер или один. В моем издании CLRS это нигде не упоминается; Мне нужно было перейти на страницу ошибок страницы, чтобы найти это. Это почти наверняка является причиной проблемы, с которой вы столкнулись с ошибкой "получить доступ за пределы диапазона", поскольку с этим инвариантом вы можете запустить сразу же массив!

Что касается анализа разбиения Хоара, я бы предложил начать, просто проследив его вручную. Здесь также более подробный анализ здесь. Интуитивно он работает, увеличивая два диапазона от концов диапазона друг к другу - один с левой стороны, содержащий элементы, меньшие, чем ось поворота, и один с правой стороны, содержащий элементы, большие, чем точка поворота. Это может быть слегка изменено для создания алгоритма разбиения Bentley-McIlroy (ссылка на ссылку), который отлично масштабируется для обработки одинаковых ключей.

Надеюсь, это поможет!

Ответ 3

Ваш последний код неверен, поскольку начальное значение j должно быть r + 1 вместо r. В противном случае ваша функция раздела всегда игнорирует последнее значение.

На самом деле, HoarePartition работает, потому что для любого массива A[p...r], который содержит не менее 2 элементов (т.е. p < r), каждый элемент A[p...j] является <= каждым элементом A[j+1...r], когда он завершается. Таким образом, следующие два сегмента, которые повторяют главный алгоритм, это [start...q] и [q+1...end]

Итак, правильный код C выглядит следующим образом:

void QuickSort(int a[],int start,int end) {
    if (end <= start) return;
    int q=HoarePartition(a,start,end);
    QuickSort(a,start,q);
    QuickSort(a,q + 1,end);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r+1;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j) 
            swap(&a[i],&a[j]);
        else 
            return j;
    }
}

Дополнительные пояснения:

• Часть раздела - это просто перевод псевдокода. (Обратите внимание, что возвращаемое значение j)

• для рекурсивной части, обратите внимание, что проверка базового регистра (end <= start вместо end <= start + 1 в противном случае вы пропустите поднабор [2 1])

Ответ 4

Последний код C работает. Но это не интуитивно. И теперь я, к счастью, изучаю CLRS. По-моему, псевдокод CLRS ошибочен (в 2e) Наконец, я считаю, что было бы правильно изменить место.

 Hoare-Partition (A, p, r)
 x ← A[p]
     i ← p − 1
     j ← r + 1
 while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
    repeat   i ←  i + 1
            until     A[i] ≥ x
    if  i < j
              exchange  A[i] ↔ A[j]
    else  
              exchnage  A[r] ↔ A[i]  
              return   i

Да, добавьте обмен A [r] ↔ A [i] может заставить его работать. Зачем? Поскольку A [i] теперь больше A [r] OR я == r. Поэтому мы должны обменять, чтобы гарантировать функцию раздела.

Ответ 5

• перемещение по центру. (например, используйте медиану из трех. переключитесь на сортировку вставки для небольшого размера ввода.)
• раздел,
  • повторная замена в настоящий момент самая левая 1 с самым правым в настоящее время 0.
    0 - cmp (val, pivot) == true, 1 - cmp (val, pivot) == false.
    остановить, если не осталось < право.
  • после этого, своп-поворот с самым правым 0.

Ответ 6

Прежде всего, вы неправильно поняли алгоритм разделения Hoare, который можно увидеть из переведенного кода в c, Так как u считается поворотным как самый левый элемент подмассива.

Поясняю, что u рассматривает самый левый элемент как ось вращения.

int HoarePartition (int a[],int p, int r) 

Здесь p и r представляют собой нижнюю и верхнюю границы массива, которые также могут быть частью большего массива (subarray).

поэтому мы начинаем с указателей (маркеров), первоначально указывающих до и после конечных точек массива (просто bcoz с использованием do while loop). Поэтому

i=p-1,

j=r+1;    //here u made mistake

Теперь в соответствии с разбиением на разделы мы хотим, чтобы каждый элемент слева от поворота был меньше или равным оси вращения и больше, чем на правой стороне оси.

Итак, мы будем перемещать маркер "i", пока не получим элемент, который больше или равен оси поворота. И аналогично "j" до тех пор, пока мы не найдем элемент, который меньше или равен оси вращения.

Теперь, если я < j мы заменяем элементы bcoz, оба элемента находятся в неправильной части массива. Таким образом, код будет

do  j--; while (a[j] <= x);                 //look at inequality sign
do  i++; while (a[i] >= x);
if  (i < j) 
    swap(&a[i],&a[j]);

Теперь, если "i" не меньше, чем "j" , это означает, что теперь нет элемента между ними для замены, поэтому мы возвращаем позицию "j" .

Итак, теперь массив после секционированной нижней половины находится от 'start to j'

верхняя половина от "j + 1 до конца"

поэтому код будет выглядеть как

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,start,q);
    QuickSort(a,q+1,end);
}

Ответ 7

Простая реализация в java.

public class QuickSortWithHoarePartition {

    public static void sort(int[] array) {
        sortHelper(array, 0, array.length - 1);
    }

    private static void sortHelper(int[] array, int p, int r) {
        if (p < r) {
            int q = doHoarePartitioning(array, p, r);
            sortHelper(array, p, q);
            sortHelper(array, q + 1, r);
        }
    }

    private static int doHoarePartitioning(int[] array, int p, int r) {
        int pivot = array[p];
        int i = p - 1;
        int j = r + 1;

        while (true) {

            do {
                i++;
            }
            while (array[i] < pivot);

            do {
                j--;
            }
            while (array[j] > pivot);

            if (i < j) {
                swap(array, i, j);
            } else {
                return j;
            }
        }

    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}