TIPOS DE ALGORITMOS

Insertion Sort

Propiedades

•      estable
•      O (1) espacio extra
•      O (n2) comparaciones y swaps
•      Adaptación: O (n) el tiempo en que casi clasificado
•      Gastos generales muy bajos
  
  
  A pesar de que es uno de los algoritmos elementales de clasificación con O (n2) peor de los casos el tiempo, ordenación por inserción es el algoritmo de elección, ya sea cuando los datos se ordenan casi (porque es de adaptación) o cuando el tamaño del problema es pequeña (debido a que ha bajos costos).

 
 
 SELECTION SORT

 Propiedades

•      no es estable
•      (1) espacio extra
•       (n2) comparaciones
•       (n) los swaps
•      no de adaptación

 DESCRIPCIÓN
 Se puede concluir que la ordenación por selección nunca debe ser usado. No se adapta a los datos de cualquier manera, por lo que su tiempo de ejecución es siempre de segundo grado.

Sin embargo, una especie de selección tiene la propiedad de reducir al mínimo el número de intercambios. En aplicaciones donde el costo de los artículos de intercambio es alto, una especie de selección muy bien puede ser el algoritmo de elección.

 BUBBLE SORT

Propiedades

•      estable
•      O (1) espacio extra
•      O (n2) comparaciones y swaps
•      Adaptación: O (n) cuando casi clasificado

 
DESCRIPCIÓN

Especie de burbuja tiene muchas de las mismas propiedades que la ordenación por inserción, pero tiene sobrecarga ligeramente superior. En el caso de los datos de cerca de clasificar, ordenar burbuja toma O (n), pero requiere al menos 2 pasa a través de los datos (mientras que la ordenación por inserción requiere algo más parecido a un pase).




SHELL SHORT


propiedades

•      no es estable
•      O (1) espacio extra
•      O (n3 / 2) hora como se muestra (ver más abajo)
•      Adaptación: O (n · lg (n)) momento en que casi clasificados

DESCRIPCIÓN

La complejidad del tiempo peor de los casos de tipo concha depende de la secuencia de incremento. Para el 1 4 13 40 121 incrementos de ..., que es lo que se usa aquí, la complejidad en tiempo es O (n3 / 2). Para otros incrementos, la complejidad de tiempo se sabe que es O (n4 / 3) y hasta O (n · LG2 (n)). Ni estrechos límites superiores de la complejidad del tiempo ni la mejor secuencia de incremento se conocen.

Debido a que tipo de shell se basa en la ordenación por inserción, una especie de shell hereda las propiedades de adaptación tipo de inserción. El adapation no es tan dramático, porque la ordenación Shell requiere un paso a través de los datos por cada incremento, pero es significativo. Para la secuencia de incremento se muestra más arriba, hay log3 (n) se incrementa, por lo que la complejidad del tiempo para los datos de casi ordenada es O (n · log3 (n)).

Debido a su bajo costo operativo, de aplicación relativamente sencilla, las propiedades de adaptación, y sub-cuadrática complejidad de tiempo, tipo concha puede ser una alternativa viable a la O (n · lg (n)) algoritmos de ordenación para algunas aplicaciones cuando los datos a ordenar es no es muy grande.


MERGE SORT

 Propiedades

•      estable
•       (n) un espacio extra para las matrices (como se muestra)
•       (lg (n)) un espacio extra para listas enlazadas
•       (n · lg (n)) el tiempo
•      no de adaptación
•      No requiere acceso aleatorio a los datos

DESCRIPCIÓN

Tipo de mezcla es muy predecible. Hace entre 0,5 * lg (n) y LG (n) comparaciones por elemento, y entre los lg (n) y 1.5 * lg (n) los swaps de cada elemento. Los mínimos se obtienen de los datos ya están ordenados, los máximos se alcanzan, en promedio, para datos aleatorios. Si se utiliza Θ (n) un espacio extra no es de interés, y luego fusionar especie es una excelente opción: es fácil de implementar, y es la única estable O (n · lg (n)) algoritmo de ordenación. Tenga en cuenta que al ordenar las listas enlazadas, fusionar tipo sólo requiere Θ (lg (n)) el espacio extra (por repetición).

Tipo de combinación es el algoritmo de elección para una variedad de situaciones: cuando la estabilidad es necesaria, al ordenar las listas enlazadas, y cuando el acceso al azar es mucho más caro que el acceso secuencial (por ejemplo, la clasificación externa en la cinta).

No existen el tiempo lineal en lugar de combinar los algoritmos para el último paso del algoritmo, pero son costosos y complejos. La complejidad se justifica para aplicaciones como la clasificación externa cuando Θ (n) un espacio extra no está disponible.


HEAP SORT

Propiedades

•      no es estable
•      O (1) de espacio extra (véase el debate)
•      O (n · lg (n)) el tiempo
•      En realidad, no adaptativa

DESCRIPCIÓN

Ordenación por montículo es fácil de implementar, realiza una operación O (n · lg (n)) en lugar de ordenar, pero no es estable.

El primer bucle, el Θ (n) "heapify" fase, pone a la matriz en orden montón. El segundo bucle, el O (n · lg (n)) "sortdown" fase, en repetidas ocasiones extrae el máximo y restaura el orden montón.

La función de sumidero que está escrito de forma recursiva para mayor claridad. Así, como muestra, el código requiere Θ (lg (n)) un espacio para la pila de llamadas recursivas. Sin embargo, la recursión de cola en el lavabo () se convierte fácilmente en iteración, lo que da la O (1) espacio obligado.

Ambas fases son un poco de adaptación, aunque no de manera especialmente útil. En el caso de casi ordenados, la fase de heapify destruye el orden original. En el caso de invertir, la fase de heapify es lo más rápido posible ya que la matriz se inicia con el fin de montón, pero luego la fase de sortdown es típico. En el caso de algunas claves únicas, hay una cierta aceleración, pero no tanto como en una especie de shell o quicksort 3-way.


QUICK SORT


Propiedades

•      no es estable
•      O (lg (n)) espacio adicional (véase el debate)
•      O (n2), pero por lo general O (n · lg (n)) el tiempo
•      no de adaptación

DESCRIPCIÓN

Cuando cuidadosamente implementado, más o menos rápido es robusto y tiene bajos costos. Cuando una especie estable, no se necesita, más o menos rápido es un excelente tipo de propósito general - aunque la versión de partición de 3 vías siempre se debe utilizar en su lugar.

A más eficiente y robusto de 2 vías método de división se da en el Quicksort es óptima por Robert Sedgewick y Jon Bentley. La partición robusta produce recursividad equilibrada cuando hay muchos valores iguales al pivote, dando garantías probabilística de O (n · lg (n)) y el tiempo de O (lg (n)) espacio para todas las entradas.

Con ambos tipos sub-realiza de manera recursiva, más o menos rápida requiere O (n) más espacio para la pila de recursión en el peor de los casos cuando la recursividad no es equilibrada. Esto es muy poco probable que ocurra, pero puede ser evitado por la clasificación de pequeñas sub-conjunto recursivamente primero y el segundo sub-array tipo es una llamada recursiva de cola, que se puede hacer con la iteración en su lugar. Con esta optimización, el algoritmo utiliza O (lg (n)) espacio extra en el peor de los casos.



QUICK SORT 3

Propiedades

•      no es estable
•      O (lg (n)) espacio extra
•      O (n2), pero por lo general O (n · lg (n)) el tiempo
•      Adaptación: O (n) tiempo en O (1) claves únicas

DESCRIPCIÓN

La variación de la partición de 3 vías de tipo rápido tiene arriba un poco mayor en comparación con la versión estándar de partición de 2 vías. Ambos tienen el mismo mejor, típico, y en el peor caso de los límites de tiempo, pero esta versión es altamente adaptable en el caso muy común de la clasificación con algunas claves únicas.

Cuando la estabilidad no es necesario, de 3 vías tipo de partición rápido es el algoritmo de propósito general de clasificación de la elección.

En resumen el algoritmo mas rápido es el quick sort 3 aunque no es muy estable, despues le sigue el heap y quick, y por ultimo el de inserción

REFERENCIAS:

http://www.sorting-algorithms.com/
http://en.wikipedia.org/wiki/Algorithm