martes, 5 de julio de 2011

Métodos de Ordenamiento

Los algoritmos de ordenamiento nos permite, como su nombre lo dice, ordenar. En
este caso, nos servirán para ordenar vectores o matrices con valores asignados
aleatoriamente.

Para poder ordenar una cantidad determinada de números almacenadas en un vector o
matriz, existen distintos métodos (algoritmos) con distintas características y
complejidad. Existe desde el método mas simple, como el Bubblesort (o Método Burbúja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

Existen dos tipos de métodos de ordenamiento, los cuáles son:

- Iterativos: Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

-Recursivos: Estos métodos son aún mas complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a si mismos, es posible que el tiempo de ejecución y de ordenación sea más optimo.

Aquí resumiré y explicaré brevemente algunos de los más importantes métodos de ordenamiento:

  • Burbuja: También llamado “bubble sort” es el más sencillo de los métodos, pero muy ineficiente. Lo que hace es que recorre el arreglo intercambiando los valores adyacentes que estén ordenados. Se recorre una y otra ves dicho arreglo hasta que sea imposible realizar cambios. Concretamente lo que hace es que agarra el valor mayor y lo recorre de posición en posición hasta ponerlo en su lugar.

    • Complejidad:

      1. O(n²)
      2. Peor caso n(n-1)/2
    • Aquí un pequeño gif explicando el método:

                          Sorting_bubblesort_anim

  • Ordenamiento por inserción: En este método, también llamado insertion sort, cuando hay n elementos, se toma el elemento n+1 y se compara con los elementos previamente ordenados, deteniéndose al detectar un elemento menor, y es aquí cuando se inserta el elemento k+1 desplazando así a los demás elementos.

      • Complejidad:

        1. O(n2) 
        2. Peor caso: Ω(n)
      • Gif explicando el método:

                          File:Insertion-sort-example-300px.gif

  • Shell sort: . Ordena subgrupos de elementos separados K unidades del arreglo original. El valor K es llamado incremento. Después de que los primeros K subgrupos han sido ordenados), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
  • Quick Sort: Este método se basa en la filosofía de “divide y vencerás”. Tiene dos fases, una de particiones y la otra de ordenamiento. En la fase de particiones, listas de dos o mas elementos son divididas en listas mas pequeñas. Todos los objetos menores al valor que fue asignado como pivote se van a una lista, y los que son mayores a otra. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
  • Merge Sort: Es otro ejemplo del principio de “divide y vencerás”. Si el vector tiene mas de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace un merge de las dos mitades ordenadas. Primero se divide en dos sublistas de aproximadamente la mitad del tamaño, se ordena cada lista recursivamente utilizando el ordenamiento por mezcla y al final las dos sublistas en una sola lista ordenada.
      • Complejidad:
        • O(n log n)
        • Peor caso: O(n log n)
      • Gif explicativo:

                             

  • Heap sort: Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo, y luego extraer el nodo que queda como nodo raíz del montículo en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento de todos los almacenados en él.
      • Complejidad: O(n log n)
      • peor caso:
      • Gif explicativo:

              Archivo:Heap sort example.gif

  • 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. Se empieza en el dígito más significativo y se avanza 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).

 

Ya viendo cada uno de éstos métodos es posible comparar la eficiencia de algunos en ésta liga: http://www.sorting-algorithms.com/ en dónde te muestran gráficamente como se comportan con datos arreglados de diferentes maneras.

 

Referencias:

Publicado por en

1 comentario:

Suscribirse a: Enviar comentarios (Atom)