Ordenación

Clasificado en Informática

Escrito el en español con un tamaño de 2,12 KB

Ordenación por inserción. Es el método de ordenación más simple. Su implementación utiliza dos bucles cada uno de los cuales puede realizar N iteraciones. Por lo tanto el algoritmo de ordenación por inserción es O(N2), es decir cuadrático. El peor de los casos se da si el vector viene ordenado en orden inverso. El mejor de los casos se da si el vector ya viene ordenado, entonces seria de orden lineal.

QuickSort. Es un algoritmo divide y vencerás. En la práctica es el algoritmo de ordenación más rápido, basado en comparaciones. Caso Peor: El caso peor ocurre cuando reiteradamente uno de los subconjuntos generados por
la partición es el vacío. El orden es cuadrático, O(N2). Como ejemplo de este caso sería un vector ya ordenado eligiendo como pivote el primer elemento. Caso Medio: El coste de una llamada recursiva se obtiene haciendo la media de los costes sobre todos los posibles tamaños de los subproblemas. En este caso el orden es el orden es O(N*log N). Mejor Caso: el pivote termina en el centro del vector (por ejemplo), dividiéndolo en dos subvectores de igual tamaño. El orden es O(N*log N)



Mergesort: utiliza la técnica recursiva divide y vencerás para obtener un tiempo de ejecución de O(N*logN). Consta de tres pasos: 1) Si el número de elementos a ordenar es 0 o 1, acabar. 2) ordenar recursivamente las dos mitades del vector. 3) mezclar las dos mitades ordenadas en un vector ordenado. El algoritmo divide y vencerás que utiliza un procedimiento de mezcla lineal tendrá en el peor, en el caso promedio e incluso en el mejor de los casos O(NlogN) ya que la mezcla lineal siempre es lineal.

Entradas relacionadas: