Блог

только что изучил и внедрил схему разделения Хоара для быстрой сортировки на Java. Работает так же хорошо, как и рекламируемый lol, но у меня просто есть пара вопросов по этому поводу. Я попытался посмотреть видео на YouTube, но не нашел ни одного, которое бы мне это хорошо объясняло.

Я думаю, что в фактическом разделе Хоара стержень должен быть первым элементом, но я использовал средний элемент в качестве стержня на всякий случай, если массив уже отсортирован. Я написал несколько комментариев в коде о том, что меня немного смущает. В основном, почему i и j установлены на 1 меньше и на 1 больше, чем low и high , если они просто увеличиваются и уменьшаются перед проверкой массива.

 public static void quicksort(int [] arr, int low, int high){
        if(low < high){
            int pivot = partition(arr, low, high);
            quicksort(arr, low, pivot);
            quicksort(arr, pivot 1, high);
        }
    }

        public static int partition(int [] arr, int low, int high){
        int i = low-1; //Why not just set i to low? 
        int j = high 1;// Why do you have to set it to high 1 and not high?
        int mid = low   (high-low)/2;
        int pivot = arr[mid];
        
        while(true){
            do {
                i  ;
            } while(arr[i] < pivot);
            do {
                j--;
            } while(arr[j] > pivot); 
            
            if( i >= j) return j;
            swap(arr, i, j);
           
        } 
    }
  

Но когда я меняю код секционирования на то, что приведено ниже, в конечном итоге он работает, казалось бы, вечно с массивами большего размера, например, с 17 разными числами, и мне нужно вручную остановить его. Странно то, что этот код будет работать для массива меньшего размера, например, с 6 числами в нем, но не для массивов большего размера. Я не могу вручную просмотреть код для массивов с большим количеством чисел, потому что я теряюсь в вызовах рекурсии.

  public static int partition(int [] arr, int low, int high){
        int i = low; 
        int j = high;
        int mid = low   (high-low)/2;
        int pivot = arr[mid];
        
        while(true){
           while(arr[i] < pivot){
               i  ;
           }
           while(arr[j] > pivot){
               j--;
           } 
            
            if( i >= j) return j;
            swap(arr, i, j);
            
        } 
    }
  

Так что просто надеюсь, что кто-нибудь может сообщить мне, почему верхний работает идеально, а нижний — нет.

Здесь важно то, что после выполнения обмена a[i] и a[j] эти два индекса сначала должны быть увеличены / уменьшены, прежде чем выполнять следующее сравнение с pivot.

Этого не происходит в вашей второй версии.

Однако это необходимо. Представьте, что в определенный момент оба a[i] и a[j] равны сводному значению (потому что есть повторяющиеся значения). Тогда произойдет обмен, но это ничего не изменит. Что еще хуже, в вашей второй версии сравнение со значением pivot снова покажет, что они равны, и мы вернемся к тому, где мы были: это становится бесконечным циклом. Однако, если есть хотя бы одно выполнение i и j-- после того, как произошел обмен, такой бесконечный цикл не произойдет.

Один из способов гарантировать, что i и j-- произойдет хотя бы один раз после обмена, — поместить их в do { } while цикл. И как только вы сделали этот выбор, очевидно, что в первый раз i должно быть на единицу меньше, чем low и j на единицу больше, чем high .

Я хотел бы объяснить этот процесс по-своему, потому что я понял, что его иногда неправильно понимают.

Цель секционирования состоит в том, чтобы переставить массив так, чтобы он был разделен на два подмассива, причем все элементы в «левой» части не больше, чем в «правой части». Помните, что предикат «не больше», потому что «меньший» может быть невозможен, если все элементы равны.

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

Теперь процесс выглядит следующим образом:

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

• сканируйте массив слева и справа, пока не найдете большой элемент слева и маленький элемент справа (записывайте сводное значение *) или пока «указатели» не встретятся;

• если инвертированная пара не найдена, вы закончили; в противном случае поменяйте местами эти два элемента и продолжите с вложенным подмассивом.

На практике значение pivot принимается за значение некоторого элемента в массиве (что обеспечивает условие непустоты). В идеале оптимальным было бы использование медианы, но получение медианы обходится дорого. Распространенной эвристикой является «медиана из трех». Среднее значение тоже может подойти, но оно имеет линейную стоимость и работает только для числовых значений.

Сканирование выполняется одно за другим. Сканирование слева, безусловно, завершится внутри массива. Правый указатель может не проходить мимо левого.

В целях отладки вы можете настроить код так, чтобы он проверял, не пересекаются ли левый и правый указатели, выполняется ли обмен с неравными указателями и не являются ли подмассивы в конце пустыми.

* Что делать, когда элемент имеет значение pivot, — это тонкость: если вы пропускаете такие элементы, чтобы избежать их замены, существует риск достичь конца массива, когда все элементы равны.