Big O - Bubble сорт

Question

Я написал две разные версии алгоритма Bubble Sort- bubbleSort, традиционная версия алгоритма, который вы увидите в учебниках, и sortIntArray, что очень похоже на bubbleSort но рекурсивно

Возможно, это мое недоразумение, но последний вызывающий алгоритм заставляет меня думать, что эффективность алгоритма отличается от пузырьковой сортировки. Может кто-нибудь объяснить мне разницу между этими двумя, если таковые имеются?

private static int[] sortIntArray(int[] arr) {

    for(int i=0; i<arr.length-1; i++) {
        if(arr[i+1]<arr[i]) { // [i-2], [i-1], [i], [i+1], [i+2]
            printArr(arr);
            int temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
            sortIntArray(arr);
        }
    }
    return arr;
}

---

private static int[] bubbleSort(int[] arr) {

    boolean swap = false;
    while(!swap) {
        swap = true;
        for(int i = 0; i<arr.length-1; i++) {
            if(arr[i+1]< arr[i]) {
                printArr(arr);
                swap = false;
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
    }
    return arr;
}

---

/**
 * Returns an unordered integer array.
 * @return
 */
private static int[] getIntArray() {
    return new int[]{54, 899, 213, 2, 43, 8, 12, 11, 111, 43, 6, 44, 83, 3458};
}

Answer 1

Я добавил статическую переменную-счетчик, которую я увеличивал с каждым проходом самого внутреннего цикла в каждом из ваших методов. Так что для sortIntArray выдержка со счетчиком будет такой:

for(int i=0; i<arr.length-1; i++) {
        o++;
        if(arr[i+1]<arr[i]) { // [i-2], [i-1], [i], [i+1], [i+2]
            ...

Я также реализовал другой метод, который по сути представлял собой Bubble, предоставленный в Википедии, и я изменил ваш генератор случайных массивов для создания массивов разных размеров:

private static int[] getIntArray() {
    int[] rand;
    if (MAX_SIZE - MIN_SIZE > 0) {
        rand = new int[new Random().nextInt(MAX_SIZE - MIN_SIZE) + MIN_SIZE + 1];
    } else {
        rand = new int[MIN_SIZE];
    }
    for (int i = 0; i < rand.length; i++) {
        rand[i] = new Random().nextInt(rand.length * 2);
    }
    return rand;
}

Вот пример результата, когда список имеет размер 50. Если вы создадите тестовый код самостоятельно, вы увидите, что реализация Wikipedia не только гарантированно сортирует, но и обеспечивает хороший тест:

Unsorted: [52, 48, 62, 47, 42, ...]
n: 50
Bubble sort: [3, 4, 6, 6, 11, ...]
O(n): 1960
Wikipedia sort: [3, 4, 6, 6, 11, ...]
O(n): 2450
Recursive sort: [3, 4, 6, 6, 11, ...]
O(n): 27391

Интересно, что ясно видно, что рекурсивная сортировка выполняет больше итераций, чем другие алгоритмы сортировки. На основании данных из 10000 сортов, которые я сбросил в CSV, также может показаться, что при максимальном размере 30 коэффициент n^2-члена равен apx. 11.3 для полинома строгого порядка 2, тогда как для максимального размера 50 он увеличился примерно до 19, что указывает на то, что не существует такого m, что m * n^2 является верхней границей сложности вашего алгоритма во время выполнения.

tl; dr: эмпирически рекурсивный алгоритм хуже, чем O(n^2) во времени.

Answer 2

На самом деле, новая реализация кажется менее эффективной. Традиционная сортировка пузырьков сравнивает каждую пару смежных элементов на каждом проходе и, по существу, отфильтровывает самый большой несортированный элемент до конца несортированной части в массиве на каждом проходе. Проходы составляют внешнюю петлю.

Ваши функции эмулируют следующую итеративную версию (которая фактически является сортировкой вставки):

for (int i = 1; i < a.size(); ++i) {
    for (int j = i; j >= 1; --j) {
        if (a[j] < a[j - 1]) {
            int tmp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = tmp;
        }
        else {
            break;
        }
    }
}

Поскольку вы вызываете рекурсивную функцию при каждом обмене, с одним и тем же массивом, и рекурсивный вызов начинает обрабатывать с одним и тем же индексом, вы, по сути, имитируете дополнительный цикл (который может потребовать сортировки обнаруженной инверсии от начала к этому точка) с помощью рекурсивных вызовов.

Подумайте об этом так: для каждой инверсии вы сталкиваетесь с рекурсивным вызовом. Если в какой-либо точке цикла у вас есть начальная отсортированная часть массива, например, пусть этот вызов функции будет f_1
2 3 7. 1 4 5 6

Где . указывает, что массив отсортирован до этой точки. Теперь обратите внимание, что когда цикл достигает 7 и 1, он меняет местами и рекурсивно вызывает функцию, и это повторяется, так что 1 в конце концов оказывается впереди (скажем, вызов, в котором это происходит, f_2), и массив становится:

1 2 3 7. 4 5 6

Обратите внимание, что f_2 находится на большей глубине, чем f_1, С этой точки зрения, f_2 не возвращается, но цикл продолжается от 1, что эффективно эмулирует f_1, но что большая часть отсортирована, что означает, что при вызове f_2 возвращает, весь массив будет отсортирован. И, следовательно, дополнительные рекурсивные вызовы перед f_2 больше ничего не делайте, но занимайте место в стеке.

Пространственная сложность вашего алгоритма наихудшая O(n^2)и сложность по времени O(n^3), которая менее эффективна, чем оригинал (Для сложности по времени рассмотрим обратно отсортированный массив размера n у которого есть n^2 инверсии, таким образом n^2 рекурсивные вызовы, каждый из которых пересекает весь массив, таким образом O(n^3)).