algorithm - iterative - c# quick sort

Quicksort: iterativo o recursivo

Question

Aprendí sobre el ordenamiento rápido y cómo se puede implementar tanto en el método recursivo como en el iterativo.
En el método iterativo:

1. Empuje el rango (0 ... n) en la pila
2. Partición de la matriz dada con un pivote
3. Pop el elemento superior.
4. Empuje las particiones (rango de índice) en una pila si el rango tiene más de un elemento
5. Haz los 3 pasos anteriores, hasta que la pila esté vacía.

Y la versión recursiva es la normal definida en wiki.

Aprendí que los algoritmos recursivos son siempre más lentos que sus contrapartes iterativas.
Entonces, ¿qué método se prefiere en términos de complejidad de tiempo (la memoria no es una preocupación)?
¿Cuál es lo suficientemente rápido para usar en el concurso de programación?
¿C ++ STL sort () utiliza un enfoque recursivo?

Answer 1

La recursión NO siempre es más lenta que la iteración. Quicksort es un ejemplo perfecto de ello. La única forma de hacer esto de forma iterativa es crear una estructura de pila. Entonces, de otra manera, haz lo mismo que hace el compilador si usamos la recursión, y probablemente harás esto peor que el compilador. También habrá más saltos si no usa la recursión (para hacer estallar y empujar valores para apilar).

Answer 2

En términos de complejidad de tiempo (asintótica), ambas son iguales.

"Recursivo es más lento que iterativo": lo racional detrás de esta afirmación se debe a la sobrecarga de la pila recursiva (guardar y restaurar el entorno entre las llamadas).
Sin embargo, estos son un número constante de operaciones, mientras que no cambian el número de "iteraciones".

Tanto la O(nlogn) rápida recursiva como la iterativa son el caso promedio O(nlogn) y el caso O(n^2) peor .

EDITAR:

solo por diversión, ejecuté un punto de referencia con el código (java) adjunto a la publicación, y luego realicé la prueba estadística de wilcoxon , para comprobar cuál es la probabilidad de que los tiempos de ejecución sean realmente distintos

Los resultados son concluyentes (P_VALUE = 2.6e-34, eso significa que la probabilidad de que sean iguales es 2.6 * 10 ^ -34 - muy poco probable). Pero la respuesta no es lo que esperabas.
El promedio de la solución iterativa fue de 408.86 ms, mientras que la recursiva fue de 236.81 ms.

(Nota: utilicé Integer y no int como argumento para recursiveQsort() ; de lo contrario, el recursivo se habría logrado mucho mejor, porque no tiene que encerrar muchos enteros, lo que también consume mucho tiempo; lo hice porque lo iterativo La solución no tiene más remedio que hacerlo.

Por lo tanto, su suposición no es cierta, la solución recursiva es más rápida (para mi máquina y Java por lo menos) que la iterativa con 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);
}