Selection Sort – Algoritmos de ordenación

Post Series: Problema #1 - Ordenación

Bienvenidos al primer post sobre los Algoritmos de ordenación. En este post veremos el primer algoritmo de ordenación para resolver el Problema #1. El Algoritmo que vamos a analizar e implementar es el Selection Sort. Como veremos en post futuros, seguiremos la estructura ya mencionada en la introducción de este Problema.

Introducción

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenación que requiere 𝜎(𝑛2) operaciones para ordenar una lista de n elementos. Analizaremos su coste más detalladamente tras ver su funcionamiento. Este Algoritmo de ordenación se basa en la sencillez dejando a un lado la eficiencia. Por eso si necesitamos un algoritmo de ordenación y tenemos que implementarlo de forma rápida y además nuestros Data Set .

Explicación

El funcionamiento es bastante intuitivo y fácil de entender.Selection Sort Funcionamiento

  1. Buscamos el mínimo elemento de la lista.
  2. Intercambiamos dicho elemento con el primero.
  3. Buscar el siguiente elemento mínimo en el resto de la lista.
  4. Intercambiarlo con el segundo.
  5. Repetir…

Tomando el caso general:

  1. Buscar el mínimo elemento entre una posición i (incluyendo la posición i) y el final de la lista.
  2. Intercambiar el mínimo con el elemento de la posición i.
  3. Aumentamos i en 1.
  4. Repetir..

Implementación

Como siempre lo implementaremos en java. Usaremos ArrayList<E> para su implementación. Ya que el acceso y colocación (get/set) y añadir (add) son de orden constante. Además de la comodidad que nos proporciona usar dicha estructura.

Análisis

Una vez que ya sabemos como funciona el algoritmo y hemos realizado su implementación, procederemos a su análisis.

Como podemos apreciar en el Código por cada elemento del array, realizamos una búsqueda del menor elemento, pero esa búsqueda por cada iteración se reduce su longitud en 1 unidad. Cada elemento es: n y la búsqueda del mínimo resulta en una progresión aritmética: (n − 1) + (n − 2) + … + 2 + 1.  Así que queda:

𝑓(𝑛)=n(n − 1) / 2 ∈ Θ(n2)

Como podemos apreciar el coste del algoritmo es cuadrático, costoso en comparación a otras soluciones que veremos en futuros post.

En definitiva en un Algoritmo sencillo, pero costoso si vamos a ordenar bastantes elementos.

Si tenéis cualquier duda o sugerencia no dudéis en comentarla.

Leave a Reply

Your email address will not be published.