Я пытаюсь понять разницу между этими двумя условиями на этапе разделения быстрой сортировки. При написании я использую однобуквенные имена переменных, чтобы их было легче читать.
В этой реализации быстрой сортировки, для простоты, скажем, pivot_idx = (L + R) // 2
, arr[high]
и arr[pivot]
меняются местами перед разделением. Таким образом, указатель L
начинается с нижнего индекса, а указатель R
начинается с индекса high - 1
. Допустим также, что указатель L
увеличивается до тех пор, пока не будет найден элемент, имеющий значение > Pivot, а следующий цикл уменьшает указатель R
до тех пор, пока не будет найден элемент <= Pivot.
Если условие while (L < R)
и мы увеличиваем указатель L
до тех пор, пока он не найдет элемент > опорной точки, то на последней итерации L
перемещается вперед, пока не встретится с R
. arr[R]
уже указывает на элемент > Pivot, поскольку arr[L]
и arr[R]
были заменены местами на предыдущем шаге. Таким образом, опорная точка должна быть правильно размещена там, где L
указывает в конце.
Моя подпись функции — partition(int[] arr, int low, int high)
. Вот пример кода, который я написал.
int pivotIdx = (low + high) / 2;
int pivotElem = arr[pivotIdx];
int r = high - 1;
int l = low;
// Swap pivot and final elem
arr[pivotIdx] = arr[high];
arr[high] = pivotElem;
while (l <= r) {
while (l <= r && arr[l] <= pivotElem) {
l++;
}
while (l <= r && arr[r] > pivotElem) {
r--;
}
if (l < r) {
int tmp = arr[l]; // bigger element
arr[l] = arr[r]; // assign smaller element to left idx
arr[r] = tmp; // assign bigger element to right idx
}
}
arr[high] = arr[l];
arr[l] = pivotElem;
Может ли это быть пока (L < R)?
Нет, не может.
Чтобы убедиться в этом, попробуйте пример, например, с int[] arr = { 8, 7 }
в качестве входных данных.
8
будет выбран в качестве опорного значения, и первоначальный обмен с конечным элементом фактически приведет массив в порядок.
Но тогда, если использовать while (l < r)
вместо while (l <= r)
, цикл while не будет введен, поэтому окончательный обмен — с неизменным l
значением, равным нулю, — вернет массив в исходное состояние вне порядка.
Код, который вы представляете (пожалуйста, представьте хотя бы полные процедуры!), не документирует, является ли
high
эксклюзивным или инклюзивным. Вы не рассказываете в прозе: читатели должны это вычесть.