Quicksort: Итеративный или рекурсивный

Ответ 1

С точки зрения (асимптотической) временной сложности - они одинаковы.

"Рекурсивный медленнее, чем итеративный" - рациональное значение этого утверждения связано с накладными расходами на рекурсивный стек (сохранение и восстановление среды между вызовами).
Тем не менее, это постоянное количество ops, не изменяя число "итераций".

И рекурсивная, и итеративная quicksort - это O(nlogn) средний случай и O(n^2) худший случай.

EDIT:

просто для удовольствия. Я провел тест с кодом (java), прикрепленным к сообщению, а затем я запустил статистический тест wilcoxon, чтобы проверить, какова вероятность того, что время выполнения действительно отличается

Результаты являются окончательными (P_VALUE = 2.6e-34, это означает, что вероятность того, что они одинаковы, равна 2.6 * 10 ^ -34 - очень маловероятно). Но ответ не тот, который вы ожидали.
Среднее значение итерационного решения составляло 408,86 мс, а рекурсивного - 236,81 мс

(Примечание. Я использовал Integer, а не int в качестве аргумента для recursiveQsort() - иначе рекурсивный достиг бы гораздо лучшего, потому что ему не нужно вставлять много целых чисел, что также требует много времени - Я сделал это, потому что итеративное решение не имеет другого выбора, кроме как делать это.

Таким образом, ваше предположение неверно, рекурсивное решение быстрее (для моей машины и java, по крайней мере), то итеративный с P_VALUE = 2.6e-34.

public static void recursiveQsort(int[] arr,Integer start, Integer end) { 
    if (end - start < 2) return; //stop clause
    int p = start + ((end-start)/2);
    p = partition(arr,p,start,end);
    recursiveQsort(arr, start, p);
    recursiveQsort(arr, p+1, end);

}

public static void iterativeQsort(int[] arr) { 
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    stack.push(arr.length);
    while (!stack.isEmpty()) {
        int end = stack.pop();
        int start = stack.pop();
        if (end - start < 2) continue;
        int p = start + ((end-start)/2);
        p = partition(arr,p,start,end);

        stack.push(p+1);
        stack.push(end);

        stack.push(start);
        stack.push(p);

    }
}

private static int partition(int[] arr, int p, int start, int end) {
    int l = start;
    int h = end - 2;
    int piv = arr[p];
    swap(arr,p,end-1);

    while (l < h) {
        if (arr[l] < piv) {
            l++;
        } else if (arr[h] >= piv) { 
            h--;
        } else { 
            swap(arr,l,h);
        }
    }
    int idx = h;
    if (arr[h] < piv) idx++;
    swap(arr,end-1,idx);
    return idx;
}
private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void main(String... args) throws Exception {
    Random r = new Random(1);
    int SIZE = 1000000;
    int N = 100;
    int[] arr = new int[SIZE];
    int[] millisRecursive = new int[N];
    int[] millisIterative = new int[N];
    for (int t = 0; t < N; t++) { 
        for (int i = 0; i < SIZE; i++) { 
            arr[i] = r.nextInt(SIZE);
        }
        int[] tempArr = Arrays.copyOf(arr, arr.length);

        long start = System.currentTimeMillis();
        iterativeQsort(tempArr);
        millisIterative[t] = (int)(System.currentTimeMillis()-start);

        tempArr = Arrays.copyOf(arr, arr.length);

        start = System.currentTimeMillis();
        recursvieQsort(tempArr,0,arr.length);
        millisRecursive[t] = (int)(System.currentTimeMillis()-start);
    }
    int sum = 0;
    for (int x : millisRecursive) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of recursive. AVG = " + ((double)sum)/millisRecursive.length);
    sum = 0;
    for (int x : millisIterative) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length);
}

Ответ 2

Рекурсия не всегда медленнее, чем итерация. Quicksort - прекрасный пример этого. Единственный способ сделать это путем итерации - создать структуру стека. Таким образом, по-другому делать то же самое, что компилятор делает, если мы используем рекурсию, и, возможно, вы сделаете это хуже, чем компилятор. Также будет больше прыжков, если вы не используете рекурсию (чтобы поп и нажать значения для стека).

Ответ 3

В общем смысле рекурсия бит медленнее, чем итеративная контр-часть, так как она вызывает загрузку/выгрузку кадров стека.

Однако для некоторых операций, стоимость которых почти всегда перегружена сложностью итеративной версии.

Рассмотрим записи рекурсивных/итерационных версий для обхода порядка двоичного дерева поиска.

Ответ 4

Это решение, которое я придумал в Javascript. Я думаю, что это работает.

 function qs_iter(items) { if (!items || items.length <= 1) { return items } var stack = [] var low = 0 var high = items.length - 1 stack.push([low, high]) while (stack.length) { var range = stack.pop() low = range[0] high = range[1] if (low < high) { var pivot = Math.floor((low + high)/2) stack.push([low, pivot]) stack.push([pivot+1, high]) while (low < high) { while (low < pivot && items[low] <= items[pivot]) low++ while (high > pivot && items[high] > items[pivot]) high-- if (low < high) { var tmp = items[low] items[low] = items[high] items[high] = tmp } } } } return items }

Дайте мне знать, если вы нашли ошибку :)