ANALISIS ALGORITMOS ORDENACION

Análisis de la complejidad
computacional de los
algoritmos de ordenación

INSERCION
Insercion(int matrix[])
{
int i, temp, j;
for (i = 1; i < matrix.length; i++)
{
temp = matrix[i];
j = i - 1;
while ( (matrix[j] > temp) && (j >= 0) )
{
matrix[j + 1] = matrix[j];
j--;
}
matrix[j + 1] = temp;
}
}
EN LA CLASE: ANALIZA EL TIEMPO DE EJECUCIÓN _ COMPLEJIDAD

SELECCION
Seleccion(int[]matrix)
{
int i,j, k, p, buffer, limit = matrix.length-1;
for(k = 0; k < limit; k++)
{
p = k;
for(i = k+1; i <= limit; i++)
if(matrix[i] < matrix[p]) p = i;
if(p != k)
{
buffer = matrix[p];
matrix[p] = matrix[k];
matrix[k] = buffer;
}
}
}
EN LA CLASE: ANALIZA EL TIEMPO DE EJECUCIÓN _ COMPLEJIDAD

Algoritmo quicksort
• La primera etapa en el algoritmo de partición es obtener
el elemento pivote;
• Una vez que seha seleccionado se ha de buscar el
sistema para situar en la sublista izquierda todos los
elementos menores que el pivote y en la sublista
derecha todos los elementos mayores que el pivote.
• Supongamos que todos los elementos de la lista son
distintos, aunque será preciso tener en cuenta los casos
en que existan elementos idénticos

• El primer problema a resolver en el diseño del algoritmo
dequicksort es seleccionar el pivote.
• Aunque la posición del pivote, en principio, puede ser
cualquiera, una de las decisiones más ponderadas es
aquella que considera el pivote como el elemento central
o próximo al central de la lista
• Veamos el siguiente ejemplo

Los pasos que sigue el algoritmo quicksort:
•

Seleccionar el elemento central de a[0:n-1] como pivote

•

Dividir los elementosrestantes en particiones izquierda y derecha,
de modo que ningún elemento de la izquierda tenga una clave
(valor) mayor que el pivote y que ningún elemento a la derecha
tenga una clave más pequeña que la del pivote.

•

Ordenar la partición izquierda utilizando quicksort recursivamente.

•

Ordenar la partición derecha utilizando quicksort recursivamente.

•

La solución es partición izquierda seguidapor el pivote y a
continuación partición derecha.

Codificación en C del algoritmo quicksort
void quicksort(double a[], int primero, int ultimo)
{
int i, j, central;
double pivote;
central = (primero + ultimo)/2;
pivote = a[central];
i = primero;
j = ultimo;
do {
while (a[i] < pivote) i++;
while (a[j] > pivote) j--;
if (i<=j)
{
double tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp; /* intercambia a[i]con a[j] */
i++;
j--;
}
}while (i <= j);
if (primero < j)
quicksort(a, primero, j);/* mismo proceso con sublista izqda */
if (i < ultimo)
quicksort(a, i, ultimo); /* mismo proceso con sublista drcha */
}

Análisis del algoritmo quicksort
El análisis general de la eficiencia de quicksort es difícil. La mejor forma de
ilustrar y calcular la complejidad del algoritmo es considerar el número decomparaciones realizadas teniendo en cuenta circunstancias ideales.
Supongamos que n (número de elementos de la lista) es una potencia de 2,

n = 2k (k = log2 n).
Además, supongamos que el pivote es el elemento central de cada lista, de
modo que quicksort divide la sublista en dos sublistas aproximadamente
iguales.
En la primera exploración o recorrido hay n − 1 comparaciones. El resultado de
la etapacrea dos sublistas aproximadamente de tamaño n/2.
En la siguiente fase, el proceso de cada sublista requiere aproximadamente n/2
comparaciones. Las comparaciones totales de esta fase son 2(n/2) = n.
La siguiente fase procesa cuatro sublistas que requieren un total de 4(n/4)
comparaciones, etc.

Eventualmente, el proceso de división termina después de k pasadas
cuando la sublista resultante tengatamaño 1.
El número total de comparaciones es aproximadamente:
n + 2(n/2) + 4(n/4) + … + n(n/n) = n + n + … + n = n · k = n · log2 n
Para una lista normal la complejidad de quicksort es O(n log2 n)
El caso ideal que se ha examinado se realiza realmente cuando la lista
(el array) está ordenado en orden ascendente. En este caso el
pivote es precisamente el centro de cada sublista.

Si el array...