Я не понимаю эту реализацию быстрой сортировки
У меня есть код для быстрой сортировки в 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 после двух внутренних whiles? Я знаю конкретные случаи для этого, но каково их математическое (или точное) свойство происходить?
Извините за дерьмовый английский, и спасибо.
PD: Проигнорируйте в этом случае оптимизацию, или выберите опору и все такое, пожалуйста.
Решение
Если при запуске a [i]> pivot (так что i не изменяется) и a [j]> pivot для всех j до a [j] = pivot, следующая итерация цикла приведет к ситуации, когда j < я.
Проиллюстрировать…
Возьмите следующий массив:
int a[] = [10, 7, 2, 6, 3];
При первом вызове быстрой сортировки, где первый равен 0, а последний равен 4 (последний индекс в массиве), pivot будет равен [2] = 2. В первой итерации, если цикл while, a [0]> 2, поэтому я не изменился. a [4]> 2, j—, a [3]> 2, j—, a [2] = 2, теперь мы нажимаем на оператор if. 0 <= 2, поэтому мы меняем местами a [0] и a [2] и выполняем i ++ и j—.
Теперь массив выглядит так:
[2, 7, 10, 6, 3]
с i = 1 и j = 1. a [i]> 2, поэтому я не изменился. a [j]> 2, поэтому j—, j теперь равно 0. a [j] не больше 2 (так как оно равно 2), а j остается на 0. Теперь у нас i = 1 и j = 0 или я> J.
Если вы заметили, 2 находится в «отсортированном» положении и больше не нуждается в перемещении. Кроме того, стержень был наименьшим элементом в массиве. Надеюсь, что это поможет вам понять это.
Другие решения
i а также j начать с любого конца массива, пока они не найдут значение, которое больше, чем сводная точка (a[i]) и меньше, чем стержень (a[j]). Когда два таких значения найдены, они поменялись местами, так что вы получите массив, где после цикла i до конца больше, чем стержень, и начало j меньше, чем стержень. Чем мы рекурсируем на этих двух подмассивах.
i>j когда список закончен, делится на сводное значение. i а также j охватил каждое значение в массиве, чтобы убедиться, что оно находится на правильной стороне оси. Это может произойти прямо в середине массива или после замены только одного значения в зависимости от того, где в списке находится сводное значение. Это может быть наибольшее или наименьшее значение, или оно может быть прямо в середине списка значений.
detector