Quicksort - разбиение Hoare с повторяющимися значениями

Question

Я реализовал классический алгоритм разбиения Hoare для Quicksort. Он работает с любым списком уникальных номеров [3, 5, 231, 43]. Единственная проблема - когда у меня есть список с дубликатами [1, 57, 1, 34]. Если я получу повторяющиеся значения, я ввожу бесконечный цикл.

private void quicksort(int[]a, int lo, int hi) { 
    if (lo < hi) { 
     int q = hoare_partition(a, lo, hi); 
     quicksort(a, lo, q - 1); 
     quicksort(a, q + 1, hi); 
    } 
} 

private int hoare_partition(int[] a, int lo, int hi) { 

    int pivot = a[hi]; 
    int i = lo; 
    int j = hi; 

    while (true) { 

     while (a[i] < pivot) i++; 
     while (a[j] > pivot) j--; 

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

Возможно ли, что реализация Хоара неверна и не может справиться с дубликатами?

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

Answer 1

algorithm partition(A, lo, hi) is 
    pivot := A[lo] 
    i := lo – 1 
    j := hi + 1 
    loop forever 
     do 
      i := i + 1 
     while A[i] < pivot 

     do 
      j := j – 1 
     while A[j] > pivot 

     if i >= j then 
      return j 

     swap A[i] with A[j] 

Псевдокод выше взят из Wikipedia. Давайте сравним его с вашим кодом.

Проблема в том, что вам нужно переместить индексы после обмена. Псевдокод использует цикл do-while вместо цикла while для перемещения индексов после свопинга. Также обратите внимание на начальные значения i и j.

algorithm quicksort(A, lo, hi) is 
    if lo < hi then 
     p := partition(A, lo, hi) 
     quicksort(A, lo, p) 
     quicksort(A, p + 1, hi) 

Для рекурсивного шага, вам, возможно, придется позаботиться о случаях края (то есть, индексы). Он должен работать, если вы меняете quicksort(a, lo, q-1) на quicksort(a, lo, q).

Полная рабочая версия, я просто написал:

import java.util.Arrays; 

public class Test { 

    public static void main(String[] args) throws Exception { 
     int[] input = {1, 57, 1, 34}; 
     quicksort(input, 0, input.length - 1); 
     System.out.println(Arrays.toString(input)); 
    } 

    private static void quicksort(int[]a, int lo, int hi) { 
     if (lo < hi) { 
      int q = hoare_partition(a, lo, hi); 
      quicksort(a, lo, q); 
      quicksort(a, q + 1, hi); 
     } 
    } 

    private static int hoare_partition(int[] a, int lo, int hi) { 

     int pivot = a[lo]; 
     int i = lo - 1; 
     int j = hi + 1; 

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

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

      if (i >= j) { 
       return j; 
      } 
      swap(a, i, j); 

     } 
    } 

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

} 

Если вы предпочитаете while петлю вместо do-while:

private static int hoare_partition(int[] a, int lo, int hi) { 

      int pivot = a[lo]; 
      int i = lo; 
      int j = hi; 

      while (true) { 

       while (a[i] < pivot) i++; 

       while (a[j] > pivot) j--; 

       if (i >= j) { 
        return j; 
       } 
       swap(a, i, j); 
       i++; 
       j--; 

      } 
     } 

Answer 2

Вот C++ пример, который реализует схему Хоара плюс медиана 3 check, дубликат проверки поворота (чтобы исключить средние значения), только используя рекурсию на более мелкой части, обращаясь назад к большей части (это предотвращает переполнение стека). Худшая временная сложность по-прежнему равна O (n^2), но для ее получения требуются довольно специфические шаблоны данных (медиана 3 должна будет последовательно отслеживать почти наименьшие или почти самые большие значения).

void QuickSort(uint32_t a[], size_t lo, size_t hi) { 
    while(lo < hi){ 
     size_t i = lo, j = (lo+hi)/2, k = hi; 
     uint32_t p; 
     if (a[k] < a[i])   // median of 3 
      std::swap(a[k], a[i]); 
     if (a[j] < a[i]) 
      std::swap(a[j], a[i]); 
     if (a[k] < a[j]) 
      std::swap(a[k], a[j]); 
     p = a[j]; 
     i--;      // Hoare partition 
     k++; 
     while (1) { 
      while (a[++i] < p); 
      while (a[--k] > p); 
      if (i >= k) 
       break; 
      std::swap(a[i], a[k]); 
     } 
     i = k++; 
     while(i > lo && a[i] == p) // exclude middle values == pivot 
      i--; 
     while(k < hi && a[k] == p) 
      k++; 
     // recurse on smaller part, loop on larger part 
     if((i - lo) <= (hi - k)){ 
      QuickSort(a, lo, i); 
      lo = k; 
     } else { 
      QuickSort(a, k, hi); 
      hi = i; 
     } 
    } 
} 

Answer 3

Вот еще один пример с в то время как цикл

private static int partition(int[] a, int start, int end){ 
    int i = start-1, j = end+1; 

    while(true){ 
     while(a[++i] < a[start]); 
     while(a[start] < a[--j]); 

     if (i >= j) return j; 
     swap(a, i, j); 
    } 
}