A continuación una lista que saque de Wikipedia de los diferentes algoritmos de ordenamiento, donde podemos encontrar el nombre, la complejidad, memoria:
Ordenamiento de inserción: Ordenación por inserción es un algoritmo iterativo que hace que n - 1 pasa a una lista de n elementos. En la primera pasada el segundo elemento de la lista desordenada se inserta en la posición adecuada para una lista ordenada que contiene los dos primeros puntos. El paso siguiente, el tercer elemento es insertado en una posición adecuada para la lista ordenada de una lista que contiene los tres primeros puntos. Después de la iteración k-ésima las primeras k + 1 elementos de la lista están en orden. El algoritmo continúa hasta que el elemento enésimo se inserta en su posición.
Imagen que demuestra el método de inserción (insertion).
El algoritmo se repite, parar un punto antes de cada pasada. El algoritmo terminacuando sólo los dos primeros puntos se comparan.
Imagen que demuestra el método de burbuja (bubble).
Ordenamiento de Shell: Ordenación Shell es una optimización de la ordenación por inserción propuesto por DL Shell. Shell señaló que la realización de una ordenación por inserción en la lista secundaria de los elementos que están separados por una distancia (un incremento) puede permitir que los elementos que se mueve más en la lista.
Para obtener una lista de n elementos [x1 ... xn], seleccione un incremento, i, y comenzar por ordenar el resultado n / i sub-listas:
[x1, x + 1, x2i + 1, ...],
[x2, x + 2, x2i + 2, ...], ...
[xi, xi + i, x2i + i, ...].
Siguiente i descenso y repetir el proceso hasta que es igual a 1.
Vídeo que demuestra el método de Shell.
Ordenamiento rápido: Ordenación rápida es un algoritmo de divide y vencerás con dos fases, una fase de partición y una fase de clasificación.
En la lista de la fase de partición de dos o más elementos se dividen en dos listas más pequeñas. Todos los elementos de la lista inferior o igual a un punto de pivote se colocan en una partición, mientras que todos los elementos de la lista inferior o igual al pivote se colocan en otra partición. En la implementación, siempre designar el primer elemento de la lista como el pivote. A la partición, mantiene punteros de búsqueda a la izquierda y la derecha y siga los pasos siguientes.
- Inicie el puntero de búsqueda a la izquierda en el segundo elemento de la lista y el puntero derecho en el último elemento de la lista.
- Mueva el puntero hacia la izquierda a la derecha hasta que encuentre un elemento mayor que el pivote o los puntos a la misma partida que el puntero derecho. Si el puntero hacia la izquierda cruza el puntero derecho de partición, la lista en el punto de cruce y dejar de fumar.
- Mueva el puntero del derecho a la izquierda hasta el cruce con el puntero hacia la izquierda o encuentra un elemento menor o igual al pivote. Si el puntero derecho cruza el puntero izquierdo de partición, la lista en el punto de cruce y dejar de fumar.
- Canje de los puntos a la que apunta a los dos punteros y vaya al paso 2.
Imagen que demuestra el método rápido (quick).
En la fase de partición, si la lista de elementos a ordenar contiene más de un elemento, la lista se divide por la mitad y el algoritmo de ordenación de mezcla se aplica a cada uno la mitad de la lista.
Al final de la fase de partición, el algoritmo tiene dos mitades ordenadas lista. La fase de fusión se une las dos mitades ordenadas en una lista. En mi implementación de este algoritmo, llevo a cabo la fusión mediante la asignación de un bloque de memoria igual al tamaño de la muestra combinada, y unificar las listas en el nuevo bloque de memoria. La asignación de un nuevo bloque de memoria significa que esta aplicaciónrequiere espacio de almacenamiento adicional equivalente al tamaño de la lista original.
Para combinar dos listas, comparar el valor más bajo en una lista con el valor más bajo en la otra lista. Quitar el más bajo de los dos valores de la lista y colocarla al final de lalista combinada. Repita este proceso hasta que no haya más elementos en cada lista.
Imagen que demuestra el método de mezcla (marge).
Ordenamiento por montículos: Ordenación por montículo es un algoritmo de dos fases, tiene una fase de construcción de la pila y una fase de promoción. Un montículo es un árbol binario con la propiedad que cada nodo es mayor que los propios hijos. Para obtener una lista de 1 .. N elementos, esto significa que el punto i es mayor que los hijos, los elementos (i / 2) y ((i/ 2) + 1).
Una vez que la pila está construida, la partida más importante será estar en la raíz de la pila. Para ordenar, simplemente cambiar el primer elemento de la lista con el punto N de la lista. Siguiente reconstruir la pila con los puntos 1 .. (N - 1). Repita el proceso de intercambio y la reconstrucción de la pila con un punto menos, hasta que sólo quedandos puntos.
/HeapSort/Heapsort_files/Heap_sort_example.gif)
Imagen que demuestra el método de montículo (heap).
Ordenamiento de Radix: El ordenamiento Radix es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. 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.
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).Ventajas:
El ordenamiento es razonablemente eficiente si el número de dígitos en las llaves no es demasiado grande.
Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas.
Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas.
Imagen que demuestra el método de radix.
Bien; 10 puntos.
ResponderEliminar