La mejor respuesta
Como tiene suficiente conocimiento de cómo funciona la ordenación rápida, como encontrar pivote, dividir la matriz actual y volver a hacer lo mismo de forma recursiva para cada submatriz, es fácil analizar la complejidad del tiempo teniendo en cuenta estas cosas:
Peor de caso:
El peor de los casos ocurre cuando en cada recursión obtenemos el siguiente pivote para dividir arreglos al final del arreglo.
Si N es la longitud de la matriz y teniendo el pivote actual en la posición inicial de la matriz,
el pivote en el último índice se identifica solo atravesando la matriz de principio a fin. Después de arreglar el pivote y dividir los subarreglos de longitud resultantes son (N-1), 1 .
De nuevo, este (N-1) el subarreglo encuentra el siguiente pivote en el último índice resultante de las particiones del arreglo con longitudes (N-2), 1 .
Este proceso se repite hasta que las longitudes finales de las submatrices son 1,1 .
Entonces, esto se puede dibujar matemáticamente en papel como
en el paso 1: con N elementos, la complejidad de tiempo para esta partición es
T (N) = N + T (N-1)
Donde T (N-1) es la complejidad de tiempo de la partición a procesarse de forma recursiva y N es el tiempo necesario para comparar N elementos con un pivote fijo.
en el paso 2: con N-1 elementos ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0 ya que el tiempo para particionar la matriz con longitud 1 es 0 sin particiones
Por lo tanto,
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Caso promedio :
En el caso promedio, el siguiente pivote divide la matriz en dos longitudes iguales (N / 2) comparando todos los elementos que dan como resultado la complejidad del tiempo N.
T (N) = 2 * T (N / 2) + N
divide ambos lados por N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Por lo tanto, T (N) / N = (T (N / 2) / (N / 2)) + 1
T (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
Como T (1) = 0
T (2) / 2 = 1
T (4) / 4 = T (2) + T (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) términos
Por lo tanto T (N) / N = log N
T (N) = NlogN
Respuesta
QuickSort es un algoritmo Divide and Conquer. Selecciona un elemento como pivote y divide la matriz dada alrededor del pivote elegido. Hay muchas versiones diferentes de quickSort que eligen el pivote de diferentes maneras.
- Elija siempre el primer elemento como pivote.
- Elija siempre el último elemento como pivote (implementado a continuación)
- Elija un elemento aleatorio como pivote.
- Elija la mediana como pivote.
El proceso clave en quickSort es una partición ( ). El objetivo de las particiones es, dado una matriz y un elemento x de la matriz como pivote, poner x en su posición correcta en una matriz ordenada y poner todos los elementos más pequeños (menores que x) antes de x, y poner todos los elementos mayores (mayores que x) después de x. Todo esto debe hacerse en tiempo lineal.
Los pasos de la ordenación rápida son:
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
Implementación de quicksort:
Quicksort(A,p,r) {
if (p
q
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x
i
j
while (True) {
repeat
j
until (A[j]
i
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
Complejidad temporal de clasificación rápida:
Peor Caso: El peor de los casos ocurre cuando el proceso de partición siempre elige el elemento más grande o más pequeño como pivote. Si consideramos la estrategia de partición anterior, donde el último elemento siempre se elige como pivote, el peor de los casos ocurriría cuando la matriz ya está ordenada en orden creciente o decreciente. A continuación se muestra la recurrencia para el peor de los casos.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
La complejidad de la recurrencia anterior es n cuadrado
Mejor caso: El mejor caso ocurre cuando el proceso de partición siempre elige el elemento medio como pivote. A continuación se muestra una recurrencia para el mejor de los casos.
T(n) = 2T(n/2) + (n)
La complejidad de la recurrencia anterior es nLogn
Caso promedio: Para hacer un análisis de casos promedio, debemos considerar todas las posibles permutación de la matriz y calcular el tiempo que toma cada permutación, lo cual no parece fácil. Podemos tener una idea del caso promedio considerando el caso en el que la partición coloca elementos O (n / 9) en un conjunto y elementos O (9n / 10) en otros conjuntos. A continuación se muestra una recurrencia para este caso.
T(n) = T(n/9) + T(9n/10) + (n)
La complejidad de la recurrencia anterior es nLogn
Complejidad espacial de quicksort :
El espacio utilizado por quicksort depende de la versión utilizada.
La versión in situ de quicksort tiene una complejidad de espacio de O (log n), incluso en en el peor de los casos, cuando se implementa con cuidado utilizando las siguientes estrategias:
- se utiliza particionamiento en el lugar. Esta partición inestable requiere espacio O (1).
- Después de la partición, la partición con la menor cantidad de elementos se ordena (recursivamente) primero, requiriendo como máximo espacio O (log n). Luego, la otra partición se ordena usando la recursividad o iteración de la cola, lo que no se agrega a la pila de llamadas. Esta idea, como se discutió anteriormente, fue descrita por R. Sedgewick y mantiene la profundidad de la pila limitada por O (log n).