Я не понимаю эту быструю сортировку

Question

У меня есть код для быстрой сортировки на C++, который отлично работает для массива неповторимых элементов. Я уверен, что многие люди здесь это знают, но кто это понимает? Позвольте мне объяснить себя лучше. Это код:

void quicksort(int a[], int first, int last){ 
    int i,j; 
    int pivot; 

    if((last -first + 1) <= 1) return; 

    pivot = a[(first+last)/2]; 
    i = first; 
    j = last; 

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

     if(i <= j){ 
      //SWAP 
      int temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 

      i++; 
      j--; 
     } 
    } 

    quicksort(a, first, j); 
    quicksort(a,i, last); 
} 

Итак, я понимаю все, кроме если на свопе. Может ли кто-нибудь сказать мне, математически, каков точный случай или множество случаев, когда i> j после двух внутренних ударов? Я знаю конкретные случаи для этого, но для чего это математическое (или точное) свойство для них?

Извините за дерьмовый английский и спасибо.

PD: Игнорируйте в этом случае оптимизацию, или выбирая стержень и все это.

Answer 1

Если при запуске с помощью [i]> поворот (так что i не изменяется) и [j]> поворот для всех j до тех пор, пока [j] = pivot, следующая итерация цикла приведет к ситуация, когда j < i.

Для иллюстрации ...

Рассмотрим следующий массив:

int a[] = [10, 7, 2, 6, 3]; 

На первом вызове сортировки, с первой равным 0, и последний из которых 4 (последний индекс в массиве), стержень будет be [2] = 2. В первой итерации, если цикл while, a [0]> 2, поэтому i не изменяется. a [4]> 2, j--, a [3]> 2, j--, a [2] = 2, теперь мы попадаем в оператор if. 0 < = 2, поэтому мы заменяем [0] и [2] и выполняем i ++ и j--.

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

[2, 7, 10, 6, 3] 

с г = 1 и у = 1. а [я]> 2, так что я не изменился. a [j]> 2, поэтому j--, j теперь равно 0. a [j] не больше 2 (так как оно равно 2), а j остается равным 0. Теперь имеем i = 1 и j = 0 , или i> j.

Если вы заметили, что 2 находится в «отсортированном» положении и больше не нужно перемещать. Кроме того, стержень был наименьшим элементом в массиве. Надеюсь, это поможет вам понять это.

Answer 2

i и j старт на любом конце массива, пока они не находят значение, которое больше, чем стержень (a[i]) и меньше, чем стержень (a[j]). Когда обнаруживаются два таких значения, они меняются местами, поэтому вы попадаете в массив, где после того, как цикл i до конца больше, чем точка поворота, а начало до j меньше, чем точка поворота. Затем мы рекурсируем по этим двум вспомогательным массивам.

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