@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;
  • Вопрос задан
  • 211 просмотров
Пригласить эксперта
Ответы на вопрос 2
@res2001
Developer, ex-admin
Алгоритм просмотрел бегло - похоже на правду.
обьясните пожалуйста почему тут такая запись

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽
28 мар. 2024, в 15:01
4000 руб./за проект
28 мар. 2024, в 14:54
1000 руб./за проект
28 мар. 2024, в 14:41
1000 руб./за проект