Quicksort Алгоритм не назначая поворот правильно

Question

Я наблюдал эту фантастическую визуализацию алгоритма быстрой сортировки: http://www.youtube.com/watch?v=Z5nSXTnD1I4

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

public void quickSort(int[] a, int left, int right) { 

    int index = partition(a, left, right); 
    if (left < index - 1) 
     quickSort(a, left, index); 
    if (index < right) 
     quickSort(a, index + 1, right); 
} 

private int partition (int[] a, int left, int right) { 
    int i = left - 1; 
    int j = right + 1; 
    int pivot = a[0]; 

    while (i < j) { 

     i++; 

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

     j--; 

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

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

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

Значения слева и справа, являются следующие:

left = 0 
right = array size - 1 

К сожалению, выход не является правильным. Проблема, похоже, заключается в моем лечении стержня. В визуализации, которую я наблюдал, инструктор физически удалил стержень и оставил указатель, указывающий ни на что. Он продолжил учебное пособие, и когда он дошел до точки, где i и j (то, что я называю левым и правым), оба указывали на то же пустое место, он вставил стержень и продолжил движение.

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

В этом коде, я работаю с входом:

4 8 1 6 3 7 2 5 

Я получаю результат:

1 3 2 6 8 7 4 5 

После «4» значения (т.е. шарнирного) сортируются по крайней начало алгоритма, я никогда не прибегаю к этому, что отбрасывает все. Кроме того, я думаю, что что-то не так с методом quickSort.

Может ли кто-нибудь дать мне несколько указателей? Благодарю.

Редактировать: Два исправления, которые были здесь, были удалены, поскольку они содержали ненужную и неправильную информацию. Один из них изменил опорную точку на: (слева + справа)/2. Это было, конечно, неправильно по причинам, объясняемым в ответах ниже.

Answer 1

Мне пришлось избавиться от перегородки, потому что вам нужны как i, так и j. Он должен выглядеть следующим образом:

public void quickSort(int[] a, int left, int right) { 

    int i = left; // Was -1 
    int j = right; // Was +1 
    int pivot = a[left + (right - left)/2]; // Pivot is the value of the middle index, not the index itself 
    while (i <= j) { // Changed terminating condition 
     // i++; Not needed 
     while (a[i] < pivot) { 
      i++; 
     } 
     // j++; Not needed 
     while (a[j] > pivot) { 
      j--; 
     } 
     if (i <= j) { // Changed terminating condition 
      swap(a, i, j); 
      i++; // You need to progress the indexes after the swap 
      j--; 
     } 
    } 

    System.out.println(Arrays.toString(a)); 
    if (left < j) { // Changed condition 
     quickSort(a, left, j); 
    } 
    if (i < right) { 
     quickSort(a, i, right); // was i + 1 
    } 
} 

Выход:

[4, 5, 1, 2, 3, 7, 6, 8] 
[1, 5, 4, 2, 3, 7, 6, 8] 
[1, 3, 2, 4, 5, 7, 6, 8] 
[1, 2, 3, 4, 5, 7, 6, 8] 
[1, 2, 3, 4, 5, 7, 6, 8] 
[1, 2, 3, 4, 5, 6, 7, 8] 
[1, 2, 3, 4, 5, 6, 7, 8] 
[1, 2, 3, 4, 5, 6, 7, 8] 

Answer 2

Я думаю, что метод partition должен вернуть j вместо i.

Другая проблема в вашем коде ваши условия остановки:

вместо двух отдельных условий я бы изменить его на одно условие:

if (left < right) { 

    do partition & recursive calls 

} 

Полный код:

public void quickSort(int[] a, int left, int right) { 
    if (left < right) { 
     int index = partition(a, left, right); 
     quickSort(a, left, index); 
     quickSort(a, index + 1, right); 
    } 
} 

private int partition (int[] a, int left, int right) { 
    int i = left - 1; 
    int j = right + 1; 
    int pivot = a[(left+right)/2]; 

    while (i < j) { 

     i++; 

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

     j--; 

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

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

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

Answer 3

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

int partition(final int[] a, final int left, final int right) { 
     // set the last element as pivot 
     final int pivot = a[right]; 
     int i = left - 1, j = left; 
     for (; j < right; j++) 
      if (a[j] < pivot) { 
       i++; 
       swap(a, i, j); 
      }  
     // swap a[i+1] and pivot 
     swap(a, i + 1, right); 
     return i + 1; 
    } 

и в методе QuickSort:

if (left < index) 
    quickSort(a, left, index-1); 
if (index < right) 
    quickSort(a, index + 1, right); 

надеюсь, что это помогает

Answer 4

int pivot = a[0]; 

должен быть

int pivot = a[left]; 

Это, с изменением swap (a, i, j); до swap (a, i--, j++); и everything appears to work fine.

Почему выше изменения:

Стержень должен быть первым элементом в диапазоне, не первый элемент.

также не должен быть в этом центре, так как здесь:

int pivot = a[(left + right)/2]; 

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

Таким образом, вы можете сказать:

swap(left, (left + right)/2); 
int pivot = a[left]; 

, которая очень похожа на выше (не идентичны), просто намного легче иметь дело с.