Быстрое замешательство

Question

Я иду через сортировщик и любую статью, которую вижу, я становлюсь более смущенным.

1) Эта реализация действительно хорошо http://gauss.ececs.uc.edu/Courses/C321/html/quicksort.java.html

Но, как я понимаю, после каждого прохода, индекс поворота находится в правильном положении.

Тогда в идеале мы должны делать следующее:

public static void Quicksort(int A[], int f, int l) 
    { 
     if (f >= l) return; 
     int pivot_index = partition(A, f, l); 
     Quicksort(A, f, pivot_index-1); //*** pivot_index-1 
     Quicksort(A, pivot_index+1, l); 
    } 

Но учебник использует Quicksort (A, F, pivot_index);.

Я на 200% уверен, что внесение изменения «pivot_index-1» не улучшит производительность и не уменьшит сложность; но просто хочу сделать, если мое понимание верное.

2) Реализация here работ; но он не размещает элемент поворота в правильном положении с каждым проходом.

Answer 1

Две реализации я видел:

• конечного индекс включительно
• индексного эксклюзивного

Quicksort(A, f, pivot_index-1); для первого случая.

Quicksort(A, f, pivot_index); предназначено для второго случая.

Выполнение Quicksort(A, f, pivot_index); в первом случае все равно приведет к сортированному списку, но сделает немного дополнительной работы.

Выполнение Quicksort(A, f, pivot_index-1); на втором корпусе , вероятно, не будет результат в полностью отсортированном списке все время.

Анализ this implementation:

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