En este articulo veremos:
Algoritmos de ordenamiento
Algoritmos O(n2)
Algoritmos O(n log n)
Una cota inferior de la ordenación por comparación de elementos
1. Algoritmos O(n2)
Algoritmo de ordenación BURBUJA
void BURBUJA(int[] A)
{
for (int j = A.Length - 1; j >= 1; j--)
for (int i = 0; i < j; i++)
if (A[i] > A[i + 1])
Swap(A, i, i + 1);
}
Propiedades:
- Realiza intercambio de elementos consecutivos
- Notar que siempre intercambia elementos de una posición i con su posición adyacente i + 1.
- Es estable
- Determinado por la propiedad anterior. Vea 1.1.
- Es W(n2) y por tanto Q(n2)
- Esto es porque independientemente de la cantidad de intercambios que haga, siempre se ejecutarán íntegramente los dos ciclos que son los que aportan n(n - 1)/2 operaciones determinando su orden cuadrático
- Si el arreglo ya está ordenado no realiza ningún intercambio
- Esto es evidente, nunca se cumpliría la condición A[i] > A[i + 1]
- Realiza ordenación en el lugar (sobre el mismo arreglo)
Mejora de este algoritmo:
Su mejora radica en que si en una pasada del ciclo más interno no se realiza intercambios terminar. Esto es debido a que si no se realiza intercambio es porque la parte que queda por ordenar ya lo está y por tanto no es necesario continuar.
void BURBUJA_MEJORADO(int[] A)
{
for (int j = A.Length - 1; j >= 1; j--)
{
bool hubo_cambio = false;
for (int i = 0; i < j; i++)
if (A[i] > A[i + 1])
{
Swap(A, i, i + 1);
hubo_cambio = true;
}
if (!hubo_cambio) break;
}
}
Algoritmo de Ordenación MINIMOS_SUCESIVOS
void MINIMOS_SUCESIVOS(int[] A)
{
for (int i = 0; i < A.Length - 1; i++)
{
int pos_min = i;
for (int j = i + 1; j < A.Length; j++)
if (A[j] < A[pos_min])
pos_min = j;
if (pos_min != i)
Swap(A, i, pos_min);
}
}
Propiedades:
- NO realiza intercambio de elementos consecutivos
- Notar que i £ pos_min y que se puede dar el caso de que i + 1 < pos_min
- NO es estable
- Para el siguiente arreglo a ordenar: 31, 1, 2, 32, 0, después de la primera pasada del ciclo más externo el arreglo quedaría 0, 1, 2, 32, 31, y desde punto hacia delante no se harían más intercambios y por tanto se invirtió el orden inicial de los elementos con valor 3.
- Es W(n2) y por tanto Q(n2)
- Esto es porque independientemente de la cantidad de intercambios que haga, siempre se ejecutarán íntegramente los dos ciclos que son los que aportan n(n - 1)/2 operaciones determinando su orden cuadrático
- Si el arreglo ya está ordenado no realiza ningún intercambio
- Esto es evidente, nunca se cumpliría la condición A[j] < A[pos_min] y por tanto pos_min siempre sería igual a i y no se cumplirá nunca la condición pos_min != i y por tanto nunca se intercambian elementos.
- Realiza ordenación en el lugar (sobre el mismo arreglo)
Algoritmo de Ordenación por Inserción
void INSERCION(int[] A)
{
for (int i = 1; i < A.Length; i++)
{
int Key = A[i];
int j = i - 1;
while (0 <= j && Key < A[j])
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = Key;
}
}
Propiedades:
- Realiza intercambio de elementos consecutivos
- A pesar de que la idea de este algoritmo es tomar el elemento i e insertarlo de forma ordenada en la subsecuencia ya ordenada A[1 .. i - 1] haciendo el corrimiento de los elementos mayores que él hasta encontrar la posición donde finalmente quedará (posición j + 1), se puede decir que esto es equivalente a ir intercambiando el elemento i son su adyacente por la izquierda (elemento i - 1) hasta encontrar la posición donde finalmente quedará ubicado.
- Es estable
- Determinado por la propiedad anterior. Vea 1.1.
- Es O(n2) para el caso peor y O(n) para el caso mejor.
- Exactamente el oren de ejecución de este algoritmo es O(n + k), n es la longitud del arreglo (se justifica su presencia debido a que el ciclo externo siempre se ejecuta n veces), y k es la cantidad de veces que se ejecuta el ciclo while. En realidad k es la cantidad de inversiones que tiene el arreglo inicial A, vea 1.1. Si el arreglo inicial ya está ordenado o casi ordenado (la cantidad de inversiones es O(1)) entonces el algoritmo INSERCION será O(n) estando en presencia del caso mejor. Si el arreglo está muy desordenado (la cantidad de inversiones es O(n2), vea 1.1) entonces INSERCION sería O(n2) estando entonces en el caso peor.
- De los algoritmos cuadráticos es el más eficiente porque:
- Es sensible con respecto al grado de desorden del arreglo inicial, los dos anteriores siempre son O(n2) independientemente de la distribución inicial de los elementos.
- Simplifica la operación de intercambia elementos haciendo los corrimientos. Esto en constante es una mejora en el orden del tiempo de ejecución.
- Realiza ordenación en el lugar (sobre el mismo arreglo)
Mejora de este algoritmo:
La mejora que se le puede aportar a este algoritmo de ordenación radica en bajar la constante. Para ello fijémonos que la comparación 0 <= j dentro del while interior no tendría sentido chequearla si de antemano tenemos el menor elemento del arreglo en su primera posición. Por tanto la mejora sería preprocesar el arreglo a ordenar poniendo su menor elemento en la posición 0. Esto mejora la constante debido a que la condición 0 <= j se ejecuta al menos n veces en todo el algoritmo (una vez al menos por iteración del ciclo externo), al poner el menor elemento al inicio (donde consumimos solo n operaciones) y suprimir la comparación de la condición del while, estamos cambiando al menos n operaciones por exactamente n operaciones y por tanto la constante del algoritmo disminuye. Cuando se hace esta mejora hay que tener cuidado con la estabilidad del algoritmo de ordenación debido a que la operación de poner el menor elemento al principio (que no es mas que la primera pasada del algoritmo MINIMOS_SUCESIVOS) puede romper la estabilidad, por tanto no se puede intercambiar el menor elemento con el primero del arreglo sino lo que hay es que correr los elementos para garantizar la estabilidad.
void INSERCION_MEJORADO(int[] A)
{
//poner el menor elemento al inicio ..
int pos_min = 0;
for (int i = 1; i < A.Length; i++)
if (A[i] < A[pos_min])
pos_min = i;
if (pos_min != 0)
{
int Key = A[pos_min];
for (int i = pos_min; i >= 1; i--)
A[i] = A[i - 1];
A[0] = Key;
}
//resto del algoritmo sin la condicion 0 <= j
for (int i = 1; i < A.Length; i++)
{
int Key = A[i];
int j = i - 1;
while (Key < A[j])
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = Key;
}
}
1.1 Algoritmos que realizan solo intercambios de elementos consecutivos
Definición 1: Sea A una secuencia de n valores. Las posiciones 1 £ i < j £ n están en inversión si A[i] > A[j].
Definición 2: Sea A una secuencia de n valores. La cantidad de inversiones de A es la cantidad de pares (i, j) tales que i y j están en inversión en A.
La cantidad de inversiones de una secuencia A de n valores varía entre 0 (A está ordenada crecientemente) y n(n - 1)/2 (A está ordenada decrecientemente). Por lo tanto la cantidad de inversiones de una secuencia de n valores es O(n2).
Teorema 1: Todo algoritmo de ordenación que realice solo intercambios de elementos adyacentes es O(n2).
Demostración: Cando se intercambian dos elementos adyacentes A[i] y A[i + 1] que cumplen que A[i] > A[i + 1] (i e i + 1 están en inversión) la cantidad de inversiones de A disminuye en 1, por tanto el caso peor es cuando hay que ir de n(n - 1)/2 inversiones hacia 0 inversiones (arreglo ordenado) disminuyendo de 1 en 1 y por tanto el algoritmo sería O(n2).
Teorema 2: Todo algoritmo de ordenación que realice solo intercambios de elementos adyacentes es Estable.
Demostración: Para cambiar el orden de aparición inicial de dos elementos iguales habría que intercambiarlos solo en el caso de ser adyacentes y esto nunca va a suceder porque no cumplen la condición de uno ser menor que el otro.
2. Algoritmos O(n log n)
Ordenación por Mezcla:
void MERGE_SORT(int[] A)
{
MERGE_SORT(A, 0, A.Length - 1, new int[A.Length]);
}
void MERGE_SORT(int[] A, int i, int j, int[] B)
{
if (i < j)
{
int m = (i + j) / 2;
MERGE_SORT(A, i, m, B);
MERGE_SORT(A, m + 1, j, B);
MERGE(A, i, j, B);
}
}
void MERGE(int[] A, int i, int j, int[] B)
{
int m = (i + j) / 2;
int k = i;
int p = i;
int q = m + 1;
while (p <= m && q <= j)
if (A[p] < A[q])
B[k++] = A[p++];
else
B[k++] = A[q++];
while (p <= m)
B[k++] = A[p++];
while (q <= j)
B[k++] = A[q++];
for (k = i; k <= j; k++)
A[k] = B[k];
}
Propiedades:
- Es Estable
- Notar que la forma de comparar A[p] < A[q] dentro del algoritmo de mezclar dos arrays ya ordenados crecientemente (MERGE) es la que garantiza la estabilidad
- Memoria Auxiliar O(n)
- Arreglo auxiliar (B) para realizar las mezclas.
- No ordena en el lugar
- Por la propiedad anterior.
- Es el que menor cantidad de operaciones realiza entre lo algoritmos de ordenación O(n log n) que estudiaremos.
- La demostración de esto está fuera de los objetivos de la asignatura
- Es Q(n log n)
- Es porque independientemente de cómo estén inicialmente los elementos en al arreglo a ordenar se realizarán siempre las mezclas. Ver el siguiente análisis del tiempo.
Análisis del tiempo:
La interpretación de la formula recursiva anterior es que para ordenar un arreglo de tamaño n se ordenan 2 arreglos de tamaño n/2 y luego se consume O(n/2 + n/2) = O(n) en realizar la mezcla.
Utilizamos la técnica del árbol para obtener la expresión del orden:
En el primer nivel (la raíz) se realizan n operaciones en mezclar los dos arreglos de longitud n/2, en el segundo nivel se consumen n/2 + n/2 = n operaciones en hacer dos mezclas de dos arreglos de longitud n/4, y así sucesivamente en cada nivel se realizan n operaciones. Como la cantidad de niveles es log2 n entonces la cantidad de operaciones es alrededor de n log2 n y por tanto el orden O(n log n)
Ordenación HEAPSORT
Este algoritmo de ordenación utiliza un heap binario para ordenar los elementos de un arreglo. En vez de crear un heap auxiliar le da estructura de heap al mismo arreglo. La estructura dada es la que el valor de cada nodo es mayor que sus dos hijos, esto garantiza que una vez dada estructura de heap al arreglo a ordenar, el mayor elemento esté en la primera posición (la posición 0). Como el mayor valor tiene que estar en la última posición intercambia el primer elemento con el último disminuyendo el tamaño del heap en uno y actualizando su estructura para repetir el mismo proceso hasta que el tamaño del heap sea 1
void HEAPSORT(int[] A)
{
//tamano_heap indica que parte de A es la que estamos
//considerando como heap
//inicialmente se considera que el heap es
//todo el arreglo A
int tamano_heap = A.Length;
//darle a A estructura de Heap donde el valor
//de cada nodo es mayor que sus dos hijos,
//quedando el mayor valor en A[0]
BUILD_HEAP(A, tamano_heap); (1)
for (int i = 1; i < A.Length; i++)
{
//intercambiar A[0] con el último valor en
//el heap que es A[tamano_heap - 1]
Swap(A, 0, tamano_heap - 1); (2)
//como el mayor valor pasó al final ya no
//se considera dentro del Heap
tamano_heap--; (3)
//actualizar el Heap, solo se hace un
//Heapify ya que donde único se viola
//la propiedad de Heap es en la raíz
HEAPIFY(A, 0, tamano_heap); (4)
}
}
Análisis del orden:
La operación (1) tiene O(n), las operaciones (2), (3) y (4) tienen orden O(1), O(1) y O(log n) respectivamente y cada una se ejecuta n veces, por tanto el orden final del algoritmo es O(n log n). Queda propuesto la demostración de que este algoritmo es Q(n log n).
Propiedades:
- Fue el primer algoritmo que surgió de los que ordenan en O(n log n)
- Es el más lento de los algoritmos O(n log n) que estudiaremos
- La demostración está fuera de los objetivos de la asignatura.
- Ordena en el lugar
- No utiliza memoria auxiliar
- No es Estable
- Queda propuesto un caso que demuestre que HEAPSORT no es estable.
Ordenación QUICKSORT:
QUICKSORT es el algoritmo de ordenación más rápido que existe. Aunque su caso peor es O(n2), la probabilidad de su ocurrencia es muy baja si tomamos algunas de sus variantes aleatorias. Su caso promedio es O(n log n) y es lo determina fuertemente su eficiencia.
La idea de este algoritmo es dividir el arreglo (o porción del arreglo) a ordenar en dos partes (no necesariamente de igual tamaño) donde cualquier elemento de la primera es menor que cualquier otro de la segunda. Esta división se realiza usando un valor del mismo arreglo a ordenar (elemento pivote). Una vez realizada esta operación, se le aplica el algoritmo recursivamente a cada una de las dos partes obtenidas.
void QUICKSORT(int[] A)
{
QUICKSORT(A, 0, A.Length - 1);
}
void QUICKSORT(int[] A, int p, int r)
{
if (p < r)
{
int q = PARTITION(A, p, r);
//ordenar los primeros q elementos
QUICKSORT(A, p, q);
//ordenar los segundos n - q elementos
QUICKSORT(A, q + 1, r);
}
}
int PARTITION(int[] A, int p, int r)
{
//elemento pivote del arreglo
int x = A[p];
int i = p - 1;
int j = r + 1;
while (true)
{
do j--; while (x < A[j]);
do i++; while (A[i] < x);
if (i < j)
Swap(A, i, j);
else
return j;
}
}
Propiedades:
- Más rápido
- La demostración no entra en los objetivos del curso
- No es estable
- Queda propuesto
- Caso peor O(n2)
- Caso promedio O(n log n)
Análisis del orden:
El tiempo de ejecución del algoritmo QUICKSORT es el siguiente y está determinado por la forma en que se fueron seleccionando los pivotes:
Su interpretación es que para ordenar n elementos hay que primero particionar el arreglo consumiendo O(n) (orden de PARTITION) y luego ordenando recursivamente dos subarreglos de longitudes q y n – q.
El caso mejor ocurre cuando q siempre es n/2 obteniéndose la misma expresión del algoritmo MergeSort y por tanto es O(n log n). En este caso siempre estaríamos picando a la mitad y por tanto se dice que siempre se pica bien el arreglo.
El caso peor es cuando q siempre es 1 (un ejemplo de ello es en nuestra estrategia simple de selección de pivote que el arreglo esté ordenado crecientemente), en este caso simpre estaríamos picando mal el arreglo. La expresión para el caso peor sería:
Donde se harían n + (n - 1) + (n - 2) + … + 2 + 1 = O(n2) operaciones.
Para analizar el caso promedio tenemos que considerar una versión aleatoria de QuickSort. Para ello en nuestra estrategia de pivote seleccionaremos un elemento aleatorio haciendo int x = A[Numero Aleatorio entre p y r]. De esta forma todas las secuencias tienen la misma probabilidad de caer en el caso peor, mejor y promedio. Otras estrategia aleatoria de selección del pivote es seleccionar de forma aleatoria tres elementos del arreglo y tomar como pivote el del medio (excluir el menor y el mayor).
La ordenación por QuickSort tiene una secuencia de particiones, unas buenas y otras malas. Ya vimos que en el caso mejor siempre picamos bien y en el peor siempre picamos mal. Ahora bien, en el caso promedio, como su nombre los indica, debe ser una secuencia de particiones buenas y malas intercaladas entre sí, e intuitivamente es muy poco probable que en el caso promedio se pique mal dos veces consecutivas. Analicemos la siguiente figura:
Si se pica mal y luego bien (porque asumimos que en el caso promedio no se puede picar mal dos veces seguidas) obtenemos en n + (n - 1) = O(n) dos subarreglos a ordenar casi de la misma longitud que los dos arreglos a ordenar que se obtienen en n = O(n) si se pica bien. Por tanto esto hace ver que el caso promedio tiene el mismo orden que el caso mejor O(n log n).
Mejora de QuickSort:
Una mejora para este algoritmo, que es aplicable también al algoritmo MergeSort, es combinarlo con el algoritmo de ordenación por inserción. Esta combinación proporciona una disminución de la constante del algoritmo.
La idea de la combinación es aplicar QuickSort mientras la longitud de los subarreglos a ordenar sea mayor que cierta longitud prefijada de antemano (una longitud que ha traído buenos resultados es 20) y luego a todo el arreglo aplicarle ordenación por inserción.
void QUICKSORT_MEJORADO(int[] A)
{
QUICKSORT_MEJORADO(A, 0, A.Length - 1);
INSERCION_MEJORADO(A);
}
void QUICKSORT_MEJORADO(int[] A, int p, int r)
{
if (20 < r - p)
{
int q = PARTITION(A, p, r);
QUICKSORT_MEJORADO(A, p, q);
QUICKSORT_MEJORADO(A, q + 1, r);
}
}
3. Una cota inferior de la ordenación por comparación de elementos
Todos los algoritmos de ordenación que hemos visto utilizan solamente comparaciones de elementos para establecer el orden a la secuencia inicial. Demostremos ahora que los algoritmos O(n log n) basados solo en comparaciones de elementos son los más eficientes en tiempo que se puedan crear. Para ello basta solo con demostrar el siguiente teorema:
Teorema 3: El orden del caso peor de todo algoritmo de ordenación que para determinar el orden de los elementos utilice solamente comparaciones, es W(n log n).
Demostración: Cualquier algoritmo de ordenación que se pretenda crear recibirá una secuencia A de n elementos y tendrá que devolver una de las n! posibles permutaciones de A que cumpla con el criterio de ordenación. Si el algoritmo a crear no conoce nada en absoluto con respecto a los elementos de la secuencia a ordenar, tendrá que inicialmente considerar como posibles soluciones a todas las n! permutaciones e ir discriminado permutaciones comparando elementos hasta llegar a la permutación a devolver. Cada vez que el algoritmo compara dos elementos Ai y Aj, el resultado de la comparación permitirá eliminar permutaciones no válidas del conjunto de permutaciones posibles. Si Ai < Aj entonces se eliminan del conjunto posible de permutaciones todas aquellas en las que Ai esté en una posición mayor que Aj, y viceversa si Ai > Aj. La figura siguiente muestra lo anterior:
De esta forma cualquier algoritmo que se cree basado solo en comparaciones tendría que moverse por este árbol binario que se forma desde la raíz (conjunto inicial de las n! posibles permutaciones) hasta una hoja (conjunto con una sola permutación a devolver como resultado de la ordenación). Este árbol binario tiene n! hojas y su altura es por tanto W(n log n) (Propuesto como demostración). Por consiguiente en el caso peor de cualquier algoritmo de ordenación por comparaciones habría que recorrer al menos la altura de este árbol y por tanto el orden para dicho caso peor sería W(n log n).
No hay comentarios:
Publicar un comentario