Как работает quicksort?

Question

[NoMoneyException]

Привет. Что-то сижу не могу вдолбиться в код quicksort'а. Принцип понимаю, но не могу понять мелочи, исключительные ситуации, в которых у нас не по 3 элемента по бокам и вообще все идельно подходит, как в обучающих статьях.
Вот например: если у нас разное количество элементов по бокам от опорного, с чем мы будем менять те, которым не нашлось пары? Еще вопрос: если у нас слева от опорного элемента 1 число, а справа 100, что мешает счетчику найти подходящий под условие элемент на другой стороне? Не могу найти ограничение в условии, которое запрещает ему перейти на другую сторону и выбрать себе элемент там. Как код поступает с элементом который равен pivot'у и можно ли сделать по другому?

Спасибо :)

public static void sort(int arr[], int s, int f) {
        if (arr == null)
            throw new IllegalArgumentException();
        if (arr.length == 0 || s > f || s < 0 || f < 0)
            return;

        int i = s;
        int j = f;
        int m = s + r.nextInt(f - s + 1);
        int pivot = arr[m];

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }

            if (s < j)
                sort(arr, s, j);
            if (f > i)
                sort(arr, i, f);
        }
    }

Answer 1

[Mercury13]

Первое.
Ваш код явно неортодоксальный, и, по-моему, он делает лишние сортировки.
UPD. Алгоритмическая сложность такого кода порядка O(n² log n), более точную границу подобрать не могу, да и имеет ли смысл?

Второе.
Пусть массив отсортирован по убыванию, слева — одно число, справа — сто, делящий 100. Скажем, 101, [100], 99…0.
Тогда i = 0, j = 101, и имеем массив 0, 100, 99…1, 101.
Теперь i = 1, j = 100; arr[i]<pivot в пролёте, arr[j]>pivot в пролёте, i<j, и проводим обмен 0, 1, 99…2, 100, 101.
На третьем шаге выходит 0, 1, 2 98…3, 99, 100, 101. И это при том, что делящий 100 и он давно встал на место.
Когда мы прокрутим итерацию до конца, массив будет полностью отсортирован по возрастанию.
Вывод: делящий элемент не обязательно будет точно делить массив, хоть многое что крутится вокруг него. И если будет сильный дисбаланс, часть элементов перейдёт из большего массива в меньший.

Answer 2

[Wataru]

1) В коде ошибка - два последних if-а, с рекурсивными вызовами, должны быть за while (i <= j), а не в нем.

Этот while-цикл - совершает разбиение элементов так, что элементы в s..j - меньше pivot, а в i..f - больше.
Поддерживается инвариант, что слева от i - только элементы меньше-равные pivot, а справа от j - больше-равные.
Мы вообще игнорируем, где в массиве pivot, берем только его значение. Неважно в центре он, или вообще первый элемент в массиве.

Сначала в цикле двигаем i до упора, пропуская меньшие элементы. Обратите внимание - сравнение строгое. По инварианту, правее j - элементы большие-равные pivot, поэтому цикл остановится всегда, если было хоть раз сдвинуто на предыдущей итерации внешнего цикла while. В противном случае - это первая итерация - и где-то в массиве есть сам pivot элемент - на нем цикл точно остановится.

Потом делаем то же самое но с другой стороны, уменьшая j. Теперь у нас следующая ситуация: arr[s..i-1
]<=pivot, arr[i]>=pivot, ???, arr[j]<=pivot, arr[j+1..f]>=pivot. После помены i-того и j-того элементов местами, мы можем сдвинуть i и j на еще одну позицию - ведь теперь новый arr[i]<=pivot, что мы и должны поддерживать в инварианте.

2 крайних случая: если i==j, то, очевидно, arr[i]==arr[j]=pivot, и можно без нарушения инварианта сдвинуть указатели. Если i>j после вложенных while - это говорит о том, что arr[j..i] == pivot, arr[j-1]<=pivot, arr[i+1]>=pivot, и можно не сортировать часть массива между j и i.

Отвечая на ваш вопрос: Если слева от pivot недостаточно элементов, то i будет указывать на pivot - и при swap-е сдвинет pivot в правый конец, за j. После этого момента между i и j может вообще не быть элемента равного pivot. Но левее i и правее j Будут те элементы, на которых циклы точно остановятся.