Algoritmo de ordenamiento Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valore
Views 47 Downloads 0 File size 706KB
Algoritmo de ordenamiento
Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote.
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos. Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956.1 Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, elordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores. Contenido [ocultar]
1 Clasificación
2 Estabilidad
3 Lista de algoritmos de ordenamiento
4 Referencias
5 Enlaces externos
[editar]Clasificación Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
La más común es clasificar según el lugar donde se realice la ordenación
Algoritmos de ordenamiento interno: en la memoria del ordenador.
Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.
Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si una clave aBC estaba antes que AbC, en el resultado ambas claves aparezcan juntas y en el orden original: aBC, AbC. Cuando los elementos son indistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Los algoritmos de ordenamiento que no son estables se pueden implementar para que sí lo sean. Una manera de hacer esto es modificar artificialmente la clave de ordenamiento de modo que la posición original en la lista participe del ordenamiento en caso de coincidencia.
Los algoritmos se distinguen por las siguientes características:
Complejidad computacional (peor caso, caso promedio y mejor caso) en términos de n, el tamaño de la lista o arreglo. Para esto se usa el concepto de orden de una función y se usa la notaciónO(n). El mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) pueden ordenar en O(kn) donde k es el tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede decir que estos algoritmos tienen un desempeño lineal, es decir O(n).
Uso de memoria y otros recursos computacionales. También se usa la notación O(n).
[editar]Estabilidad Los algoritmos de ordenamiento estable mantienen un relativo preorden total. Esto significa que un algoritmo es estable solo cuando hay dos registros R y S con la misma clave y con R apareciendo antes que S en la lista original. Cuando elementos iguales (indistinguibles entre sí), como números enteros, o más generalmente, cualquier tipo de dato en donde el elemento entero es la clave, la estabilidad no es un problema. De todas formas, se asume que los siguientes pares de números están por ser ordenados por su primer componente:
(4, 1)
(3, 7)
(3, 1)
(5, 6)
En este caso, dos resultados diferentes son posibles, uno de los cuales mantiene un orden relativo de registros con claves iguales, y una en la que no:
(3, 7)
(3, 1)
(4, 1)
(5, 6)
(orden mantenido)
(3, 1)
(3, 7)
(4, 1)
(5, 6)
(orden cambiado)
Los algoritmos de ordenamiento inestable pueden cambiar el orden relativo de registros con claves iguales, pero los algoritmos estables nunca lo hacen. Los algoritmos inestables pueden ser implementados especialmente para ser estables. Una forma de hacerlo es extender artificialmente el cotejamiento de claves, para que las comparaciones entre dos objetos con claves iguales sean decididas usando el orden de las entradas original. Recordar este orden entre dos objetos con claves iguales es una solución poco práctica, ya que generalmente acarrea tener almacenamiento adicional. Ordenar según una clave primaria, secundaria, terciara, etc., puede ser realizado utilizando cualquier método de ordenamiento, tomando todas las claves en consideración (en otras palabras, usando una sola clave compuesta). Si un método de ordenamiento es estable, es posible ordenar múltiples ítems, cada vez con una clave distinta. En este caso, las claves necesitan estar aplicadas en orden de aumentar la prioridad. Ejemplo: ordenar pares de números, usando ambos valores
(4, 1)
(3, 7)
(3, 1)
(4, 6) (original)
(4, 1)
(3, 1)
(4, 6)
(3, 7) (después de ser ordenado por el segundo
valor)
(3, 1)
(3, 7)
(4, 1)
(4, 6) (después de ser ordenado por el primer
(3, 1)
(4, 1)
(4, 6) (después de ser ordenado por el primer
(4, 1)
(4, 6)
(3, 7) (después de ser ordenando por el segundo
valor)
Por otro lado:
(3, 7) valor) (3, 1) valor,
el orden por el primer valor es perturbado) [editar]Lista
de algoritmos de ordenamiento
Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional. Estables
Nombre traducido
Nombre original
Complejidad
Memoria Método
Ordenamiento de burbuja
Bubblesort
O(n²)
O(1)
Intercambio
Ordenamiento de burbuja bidireccional
Cocktail sort
O(n²)
O(1)
Intercambio
Ordenamiento por inserción
Insertion sort
O(n²)
O(1)
Inserción
Ordenamiento por casilleros
Bucket sort
O(n)
O(n)
No comparativo
Ordenamiento por cuentas
Counting sort
O(n+k)
O(n+k)
No comparativo
Ordenamiento por mezcla
Merge sort
O(n log n)
O(n)
Mezcla
Ordenamiento con árbol binario
Ordenamiento Radix
Binary tree sort
O(n log n)
O(n)
Pigeonhole sort
O(n+k)
O(k)
Radix sort
O(nk)
O(n)
Distribution sort
O(n³) versión recursiva
O(n²)
Gnome sort
O(n²)
Inserción
No comparativo
Inestables
Nombre traducido
Nombre original
Complejidad
Memoria Método
Ordenamiento Shell
Shell sort
O(n1.25)
O(1)
Inserción
Comb sort
O(n log n)
O(1)
Intercambio
Ordenamiento por selección
Selection sort
O(n²)
O(1)
Selección
Ordenamiento por montículos
Heapsort
O(n log n)
O(1)
Selección
Smoothsort
O(n log n)
O(1)
Selección
Quicksort
Promedio: O(n log n), peor caso: O(n²)
O(log n) Partición
Several Unique Sort
Promedio: O(n u), peor caso: O(n²); u=n; u = número único de registros
Ordenamiento rápido
Cuestionables, imprácticos
Nombre traducido
Nombre original
Complejidad
Bogosort
O(n × n!), peor: no termina
Pancake sorting
O(n), excepto en máquinas de Von Neumann
Memoria Método
Randomsort
[editar]Referencias 1. ↑ Bubble Sort: An archaeological algorithm analysis. Owen Astrachan
[editar]Enlaces
externos
Explicación de los distintos métodos de ordenamiento en Java. (pdf)
Discusión sobre varios algoritmos de ordenación y sus características (licencia GFDL) (pdf)
Animación de algoritmos de ordenamiento
Animación de algoritmos de ordenamiento (en inglés)
ALT: Algorithm Learning Tool. Herramienta de apoyo a la enseñanza de algoritmos que muestra gráficamente su funcionamiento. Permite implementar algoritmos propios y realizar una ejecución dinámica e interactiva
Códigos de Ordenamiento en Python
Algoritmos de Ordenamiento Debido a que las estructuras de datos son utilizadas para almacenar información, para poder recuperar esa información de manera eficiente es deseable que aquella esté ordenada. Existen varios métodos para ordenar las diferentes estructuras de datos básicas. En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casos sólo una vez. Hay métodos muy simples de implementar que son útiles en los casos en dónde el número de elementos a ordenar no es muy grande (ej, menos de 500 elementos). Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son más eficientes en cuestión de tiempo de ejecución. Los métodos sencillos por lo general requieren de aproximadamente n x n pasos para ordenar n elementos. Los métodos simples son: insertion sort (o por inserción directa) selection sort, bubble sort, y shellsort, en dónde el último es una extensón al insertion sort, siendo más rápido. Los métodos más complejos son el quick-sort, el heap sort, radix y address-calculation sort. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente. Se ha dicho que el ordenamiento puede efectuarse moviendo los registros con las claves. El mover un registo completo implica un costo, el cual se incrementa conforme sea mayor el tamaño del registro. Es por ello que es deseable evitar al máximo el movimiento de los registros. Una alternativa es el crear una tabla de referencias a los registros y mover las referencias y no los datos. A continuación se mostrarán los métodos de ordenamiento empezando por el más sencillo y avanzando hacia los mas sofisticados La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2. Análisis de Algoritmos Notación de Orden Una función f(n) se define de orden O(g(n)), es decir, f(n) = O(g(n)) si existen constantes positivas n0 y c tales que: | f(n) | = c * n0
100 n3 => O(n3) 6n2 + 2n + 4 => O(n2) 1024 => O(1) 1+2+3+4+...+n-1+n= n * (n+1)/2 = O(n2) Insertion Sort Este es uno de los métodos más sencillos. Consta de tomar uno por uno los elementos de un arreglo y recorrerlo hacia su posición con respecto a los anteriormente ordenados. Así empieza con el segundo elemento y lo ordena con respecto al primero. Luego sigue con el tercero y lo coloca en su posición ordenada con respecto a los dos anteriores, así sucesivamente hasta recorrer todas las posiciones del arreglo. Este es el algoritmo: Procedimiento Insertion Sort Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[]. paso 1: [Para cada pos. del arreglo] paso 2: [Inicializa v y j] paso paso paso paso paso
3: 4: 5: 5: 6:
For i = j) break; swap(a,i,j); }
swap(a,i,r); quicksort(a,l,i-1); quicksort(a,i+1,r); } }
a = {a,s,o,r,t,i,n} aiortsn ainrtso ainotsr ainorst
Ordenamiento de raíz (radix sort). Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Por ejemplo el número 235 se escribe 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades. Reglas para ordenar.
Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números.
El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales).
Este mismo principio se toma para Radix Sort, para visualizar esto mejor tenemos el siguiente ejemplo. En el ejemplo anterior se ordeno de izquierda a derecha. Ahora vamos a ordenar de derecha a izquierda. Archivo original. 25 57 48 37 12 92 86 33
Asignamos colas basadas en el dígito menos significativo. Parte delantera Parte posterior 0 1 212 92 333
4 525 686 757 37 848 9 10 Después de la primera pasada: 12 92 33 25 86 57 37 48 Colas basadas en el dígito más significativo.
Parte delantera Parte posterior 0 112 225 333 37 448 557 6 7 886 992 10
Archivo ordenado: 12 25 33 37 48 57 86 92
ASORTINGEXAMPLE AEOLMINGEAXTPRS AEAEGINMLO AAEEG AA AA EEG EE INMLO LMNO LM NO STPRX SRPT PRS RS #include #include #define NUMELTS 20 void radixsort(int x[], int n) { int front[10], rear[10]; struct { int info; int next;
} node[NUMELTS]; int exp, first, i, j, k, p, q, y; /* Inicializar una lista viculada */ for (i = 0; i < n-1; i++) { node[i].info = x[i]; node[i].next = i+1; } /* fin del for */ node[n-1].info = x[n-1]; node[n-1].next = -1; first = 0; /*first es la cabeza de la lista vinculada */ for (k = 1; k < 5; k++) { /* Suponer que tenemos n£meros de cuatro dÁgitos */ for (i = 0; i < 10; i++) { /*Inicializar colas */ rear[i] = -1; front[i] = -1; } /*fin del for */ /* Procesar cada elemento en la lista */ while (first != -1) { p = first; first = node[first].next; y = node[p].info; /* Extraer el kâsimo dÁgito */ exp = pow(10, k-1); /* elevar 10 a la (k-1)âsima potencia */ j = (y/exp) % 10; /* Insertar y en queue[j] */ q = rear[j]; if (q == -1) front[j] = p; else node[q].next = p; rear[j] = p; } /*fin del while */ /* En este punto, cada registro est en su cola bas ndose en el dÁgito k Ahora formar una lista £nica de todos los elementos de la cola. Encontrar el primer elemento. */ for (j = 0; j < 10 && front[j] == -1; j++); ; first = front[j]; /* Vincular las colas restantes */ while (j