Правильно ли я понял алгоритм быстрой сортировки?

Question

[Den4_x]

public static void quickSort(int[] array, int low, int high) {

        //Если массив состоит из одного эл-та(low=high) 
        //Или, если введены неверные индексы(low>high),
        //То функция не сработает!
        if (low >= high) {
            return;
        }

        //Ставим маркеры(L и R)
        int L = low;
        int R = high;

        //index среднего эл-та в массиве
        int separator = L - (L - R) / 2;

        //маркеры не должны пересекаться
        while (L < R) {
            while ((array[L] <= array[separator]) && L < separator) {
                L++;
            }
            while ((array[separator] <= array[R]) && R > separator) {
                R--;
            }
            if (L < R) {
                swap(array, L, R);
                //Если маркер  L добрался до опорного эл-та раньше, чем маркер R, то
                if (L == separator) {
                    separator = R;
                //Если маркер  R добрался до опорного эл-та раньше, чем маркер L, то 
                } else if (R == separator) {
                    separator = L;
                }
            }
        }
        //Cортируем левую часть от опорного эл-та и правую
        //(таким же сценарием, что и выше)
        //И в итоге получаем, ОТСОРИРОВАННЫЙ массив!
        quickSort(array, low, separator);
        quickSort(array, separator + 1, high);
    }

Почему тут такая запись, а не, скажем, (L+R)/2, или еще проще: R>>1?

//index среднего эл-та в массиве
int separator = L - (L - R) / 2;

Comments

[Roman]

Den4_x,
Объяснение (видео)
Конспект (текст) посложнее

Совсем просто

Answer 1

[res2001]

Алгоритм просмотрел бегло - похоже на правду.

обьясните пожалуйста почему тут такая запись

Я бы написал так:
int separator = L + (R - L) / 2;
Впрочем, обе записи эквивалентны, но мой вариант понятней.
Подразумевается, что L может быть любым 0 <= L < R.
Предложенные вами варианты дают не правильный результат при L > 0. Проверьте.
separator - целочисленный индекс середины заданного диапазона

Answer 2

[Wataru]

Такая форма получения среднего в диапазоне от L до R берется, чтобы не было переполнения.

L+(R-L)/2 = L-(L-R)/2 = (L+R)/2. Да тут в зависимости от четностей может быть разница +-1, но это не важно. Но в последнем выражении L+R может переполнится, если L и R большие, хотя результат всегда помещается в int.

Comments

[res2001]

L+(R-L)/2 == L-(L-R)/2 != (L+R)/2

Нет тут никакой защиты от переполнения. Переполнения тут быть не может в обеих формах записи (третью не рассматриваю, т.к. она не верна). Если принять, что входные параметры изначально корректные: 0 <= low <= high. Корректность почти гарантируется первым if, не хватает только проверки на low >= 0.

[Wataru]

res2001, Вы, наверно, неправильно прочитали что-то.

третью не рассматриваю, т.к. она не верна

Это школьная математика, наверно, 9 класс максимум:
L+(R-L)/2 = 2L/2+(R-L)/2 = (2L+R-L)/2 = (L+R)/2

Как раз чаще всего третью форму и используют - когда вам надо взять середину интервала, вы просто берете среднее арифметическое его концов. Это кажется очевидным.

Выражение, про которое спрашивает автор вопроса - лучше, потому что там, как вы и сказали, не может быть переполнения. И делает оно тоже самое - ищет середину массива. Но оно менее понятно, чем среднее арифметическое концов, раз автор задает про него вопрос.

[res2001]

wataru, Хех, вы правы. Плюсую