Почему на этапе разделения быстрой сортировки используется одно условие остановки с двумя указателями L и R, а (L <= R)? Может ли это быть пока (L < R)?

Я пытаюсь понять разницу между этими двумя условиями на этапе разделения быстрой сортировки. При написании я использую однобуквенные имена переменных, чтобы их было легче читать.
В этой реализации быстрой сортировки, для простоты, скажем, 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;

Код, который вы представляете (пожалуйста, представьте хотя бы полные процедуры!), не документирует, является ли high эксклюзивным или инклюзивным. Вы не рассказываете в прозе: читатели должны это вычесть.

greybeard 23.08.2024 08:54
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
1
50
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Может ли это быть пока (L < R)?

Нет, не может.

Чтобы убедиться в этом, попробуйте пример, например, с int[] arr = { 8, 7 } в качестве входных данных.

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

Но тогда, если использовать while (l < r) вместо while (l <= r), цикл while не будет введен, поэтому окончательный обмен — с неизменным l значением, равным нулю, — вернет массив в исходное состояние вне порядка.

Другие вопросы по теме