Быстрая сортировка логики

Question

Я пытаюсь реализовать быстро сортировать в java и у меня есть одно сомнение. Так вот мой быстрый сортировочный код:

package com.sorting; 

public class QuickSort implements Sort { 

@Override 
public int [] sort(int[] arr) { 
    return quickSort(arr, 0, arr.length - 1); 
} 

private int [] quickSort(int[] numbers, int low, int high) { 

    if (low < high) { 
     int q = partitionTheArrayAroundPivot(numbers, low, high); 

     if (low < q) 
      quickSort(numbers, low, q); 

     if ((q+1) < high) 
      quickSort(numbers, q + 1, high); 
    } 

    return numbers; 
} 

private int partitionTheArrayAroundPivot(int[] numbers, int low, int high) { 

    int pivot = selectPivot(numbers, low, high); 
    int i = low; 
    int j = high; 

    while (true) { 

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

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

     if (i <= j) { 
      swap(numbers, i, j); 
      i++; 
      j--; 
     } else { 
      return j; 
     } 

    } 

} 

private int selectPivot(int[] numbers, int low, int high) { 
    return numbers[high]; 
} 

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

} 

Сомнение 1: Мы продолжаем увеличение индекса я, пока мы не попали число, которое> = стержень

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

Аналогично мы продолжаем снижение индекса j до мы попали в число, которое < = стержень

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

Таким образом, это означает, что оба индекса будут также выйти из петля, если оба удара поворачиваются в двух разных местах, например. 1,0,1 здесь, если ось равна 1, тогда i будет равна 0, а j будет равно 2. И будет выполнено условие ниже , если (i < = j) { .... } , но в этом случае он не сможет сортировать вышеупомянутый массив (1,0,1), потому что после замены мы увеличиваем i и уменьшаем j, поэтому значение становится i = j = 1. После этого i будет ударять по третьему элементу, т.е. 1, и будет снова выходят из цикла со значением i = 2 и аналогично j = 0, и мы не сможем сортировать массив.

Итак, где проблема? Я что-то упускаю?

Answer 1

Я бы переписать код немного, так что selectPivot возвращает индекс вместо:

private int selectPivotIndex(int[] numbers, int low, int high) { 
    return high; 
} 

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

private int partitionTheArrayAroundPivot(int[] numbers, int low, int high) { 

    int pivotIndex = selectPivotIndex(numbers, low, high); 

    swap(numbers, pivotIndex, high); // Not needed if selectPivotIndex always returns high 
    int newPivotIndex = low; 
    for(int i = low; i < high; i++) 
    { 
     if(numbers[i] < numbers[pivotIndex]) 
     { 
      swap(numbers, i, newPivotIndex); 
      newPivotIndex++; 
     } 
    } 
    swap(numbers, newPivotIndex, pivotIndex); 

    return newPivotIndex; 
} 

Наконец, небольшая корректировка должна быть сделана в методе quickSort так, что мы не до конца в вечном петля:

if (low < q) 
     quickSort(numbers, low, q - 1); 

Этот подход ИМХО легче понять и отладить, надеясь, что он сработает для вас.

Answer 2

Использование
while (numbers[i] <= pivot) и while (numbers[j] >= pivot) и ваш код будет работать