Cargando...
 
Imprimir

Ordenación por selección directa (SelectionSort)

Image
El algoritmo de ordenación por el método de selección directa es un algoritmo relativamente sencillo y uno de los más fáciles de recordar e implementar.

Se basa en realizar varias pasadas, intentando encontrar en cada una de ellas el elemento que según el criterio de ordenación es mínimo y colocándolo posteriormente en su sitio.

A efectos prácticos, no suele dar resultados buenos si se compara con otros métodos de ordenación. Realiza una enorme cantidad de comparaciones, pero en contrapartida, muy pocos intercambios. Eso hace que su utilización se restrinja en general a dos situaciones: o bien necesitamos un algoritmo sencillito para ordenar unos pocos datos y cogemos éste mismo que no está mal y es facil de recordar, o bien tenemos una situación en la cual escribir en el array es mucho más gravoso que leer, como puede ser un escenario en el que intervengan determinados dispositivos de almacenamiento o memorias tipo flash, eeprom, etc. para el soporte de los datos.

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).

Es un algoritmo no estable de ordenación interna y su complejidad temporal en el peor caso es del orden de O(n2) y en el mejor caso -que el array ya esté totalmente ordenado- pues también es Ω(n2) siendo n el tamaño del array a ordenar... el caso es que éste algoritmo siempre hace el mismo número de comparaciones e intercambios para un n dado... así que no aprovecha una posible ordenación parcial del array. En cuanto a la complejidad espacial, es muy ahorrativo: tan solo necesita una variable temporal para realizar los intercambios, así que su gasto de memoria es constante, sea cual sea el tamaño del array. Aunque se suele utilizar para ordenación interna, puede usarse para ordenación externa si nos es imprescindible una complejidad espacial constante y muy baja. Esa situación no suele darse, excepto, quizá, en pequeños dispositivos dotados de una cantidad de memoria principal muy muy reducida y en los que además, los datos estén en un soporte cuya lectura sea mucho más rápida que la escritura.

El algoritmo consiste en realizar varias pasadas sobre el array, logrando que en cada pasada el elemento de menor valor se coloque al principio del array en un solo intercambio. En cada pasada se recorre la parte no ordenada del array realizando comparaciones con objeto de buscar el elemento de menor valor?. Una vez localizado, se intercambia por el primer elemento de la parte no ordenada, y entonces ya está en orden. Por eso, se suele implementar con dos bucles, uno anidado dentro del otro. El bucle exterior realiza las pasadas y el interior localiza el menor elemento.

Vamos a intentar ver informalmente el funcionamiento del algoritmo. Supondremos que el array tiene n elementos.

  • Realizaremos n-1 pasadas. En cada una de ellas lograremos que el elemento de menor valor se sitúe al principio. El motivo de realizar n-1 pasadas y no n es que si en cada pasada logramos ordenar un elemento, cuando tengamos en orden los n-1 del principio del array el elemento que queda al final del array es necesariamente el que nunca ha sido escogido como más pequeño de todos... es decir, es el más grande, y directamente se ha quedado el último.
  • En cada pasada recorreremos el array empezando por el elemento que aún no tengamos en orden (en la primera pasada lo revisamos todo, pero en la segunda ya empezamos por el segundo elemento, ya que el primero estará en orden... y así sucesivamente), buscando el menor de todos los elementos que aún están sin ordenar. Cuando se haya localizado ese elemento, se intercambia con el primero de la parte sin ordenar.
  • En la primera pasada, buscaremos el mínimo entre los n elementos. Cuando lo encontremos, lo ponemos en el primer lugar, y el elemento que había en primer lugar lo ponemos en el hueco que dejó ese. Como es el mínimo, habremos logrado poner en orden un elemento y nos quedan los n-1 siguientes.
  • En la segunda pasada, buscaremos el mínimo entre los n-1 elementos que nos quedan por ordenar. Cuando lo encontremos lo intercambiamos con el elemento de la segunda posición. Ya tendremos ordenados dos elementos y nos quedarán n-2 por ordenar.
  • En la tercera pasada haremos lo mismo con los n-2 últimos elementos, logrando colocar el tercer elemento en orden... y así sucesivamente, hasta que tengamos colocados todos menos uno (n-1). Cuando estemos en esa situación, el último elemento también estará en orden, ya que será el más grande de todos, porque en ninguna de las n-1 pasadas ha sido escogido como mínimo.

Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo de selección directa: 45, 52, 21, 37, 49, así pues, n=5

1ª pasada: buscamos entre los últimos n (es decir, 5) elementos el menor de todos, y lo intercambiaremos con la primera posición.

45, 52, 21, 37, 49 → Para buscar el menor, necesitaremos un bucle for que recorra los n últimos elementos.
45, 52, 21, 37, 49 → El menor es el 21, colocado en tercera posición.
45, 52, 21, 37, 49 → Lo intercambiamos con el de la primera posición.
21, 52, 45, 37, 49 → Ya tenemos uno en orden. Nos quedan los n-1 últimos.

2ª pasada: buscamos entre los últimos n-1 (es decir, 4) elementos el menor de todos, y lo intercambiaremos con la segunda posición.

21, 52, 45, 37, 49 → Recorremos los cuatro últimos y el menor es el 37.
21, 37, 45, 52, 49 → Lo intercambiamos con la segunda posición y ya hay dos en orden.

3ª pasada: buscamos entre los últimos n-2 (es decir, 3) elementos el menor de todos, y lo intercambiaremos con la tercera posición.

21, 37, 45, 52, 49 → El menor es el 45, en tercera posición.
21, 37, 45, 52, 49 → El 45 ya estaba en 3ª posición, así que al intercambiarlo con él mismo, se queda donde está. Ya tenemos tres en orden.

4ª y última pasada: buscamos entre los últimos n-3 (es decir, 2) elementos el menor de todos, y lo intercambiaremos con la cuarta posición.

21, 37, 45, 52, 49 → El menor es el 49, en quinta posición.
21, 37, 45, 49, 52 → Lo intercambiamos con la cuarta posición. Ya hay cuatro en orden.
21, 37, 45, 49, 52 → El último está necesariamente en orden también.



Expresado en pseudocódigo, podría ser algo como esto:

pseudocódigo
algoritmo seleccion( A : array de n elementos indizados de 1 a n)
  para i desde 1 hasta n-1 hacer: //las n-1 pasadas
       //seleccionar el mínimo e intercambiarlo
       //con el elemento de la posición i
       //Supondremos que el menor es el primero
       posMin=i
       //buscamos uno menor aun
       para j desde i+1 hasta n hacer:   //el recorrido
         si A[j] < A[posMin] entonces //Si es menor aun
           posMin=j //tomamos nota
       fin para
       //Ya sabemos cual es el minimo.
       //lo ponemos en la posición i
       intercambiar A[i] y A[posMin]
  fin para
fin algoritmo


Como se puede apreciar, el intercambio se realiza en el bucle exterior. Así pues, se realizan n-1 intercambios. Sin embargo, en el bucle interior se realizan las comparaciones. Hay muchísimas más comparaciones que intercambios.

También hay que tener en cuenta que por supuesto, es necesario adaptarlo a las necesidades concretas. Por ejemplo, en C/C++/C#/Java, etc... los índices de los arrays empiezan en 0 y terminan en n-1. El array a ordenar no tiene por qué ser de enteros, puede ser de cualquier cosa ordenable, pero entonces, análogamente, la operación de comparación (">") debe ser sustituida por la operación que nos compare nuestros elementos por el criterio que nosotros queramos.

Para verlo de manera un poco más gráfica, aquí tienes ésta animación de baja tecnología:
Reproductor Flash no disponible.


(La música es New Era Rag de James Scott, obtenida de la página de Warren Trachtman(external link). Gracias, Warren)

Ojo con los índices

Lo importante de un algoritmo no es que lo memorices ni que lo intentes traducir literalmente a un lenguaje de programación concreto. Lo importante es que lo entiendas y seas capaz de implementarlo adaptándolo a cualquier lenguaje sin traducirlo literalmente.

Con el pseducódigo de arriba hay un importante reto que a veces es dificil de superar: los índices. En el pseudocódigo se asume que el array de n elementos se indiza desde 1 hasta n. Es decir, el primer elemento es el número 1 y el último es el número n.

En algunos lenguajes de programación (como Pascal o Delphi, por ejemplo) es posible utilizar arrays que empiecen por un índice 1, como en el pseudocódigo. Sin embargo, en muchos otros (como C/C++/C# o Java) los arrays siempre empiezan por el índice 0. Es decir los elementos de un array de n elementos se indizan con índices que empiezan en 0 y terminan en n-1. Para salvar ese obstáculo, lo más sencillo suele ser prestar atención y tenerlo en cuenta al declarar los bucles y sus condiciones.

Por ejemplo, para implementarlo en C# optamos por hacer que el bucle exterior vaya desde 0 hasta n-2 (Es decir, hemos restado una unidad con respecto al pseudocódigo). En el interior, también lo tenemos en cuenta, y terminamos en n-1 (porque el array va de 0 a n-1, y no de 1 a n).

C# - Ordenación por selección directa
static void SeleccionEnteros(int[] A)
{
      //El tamaño del array
      int n = A.Length;
      //las n-1 pasadas. En la primera pasada
      //i=0, y en la última i=n-2
      for (int i = 0; i < n - 1; i++)
      {
          //Buscamos el mínimo
          //supondremos que es el primero
          int posMin = i;
          //nos movemos por el resto
          for (int j = i+1; j < n; j++)
          {
              //si este es menor aun
              if (A[j] < A[posMin])
              {
                  //tomamos nota de su posición
                  posMin = j;
              }
          }
          //intercambiar la posición i y el
          //mínimo encontrado
          int iaux = A[i];
          A[i] = A[posMin];
          A[posMin] = iaux;
      }
}


¿Y con objetos?

Pues ningún problema. Primero, necesitamos tener un criterio claro de ordenación, y que algún método nos permita saber dados dos objetos si están en orden o no. Mira cómo lo hicimos con el algoritmo de la burbuja. Lo mismo se puede aplicar con la selección directa.

Optimizaciones

No hay prácticamente optimizaciones posibles para éste método.

A algún listo se le ha ocurrido alguna que otra vez que se puede aprovechar la búsqueda del mínimo para encontrar también el máximo... y luego, al final de cada pasada poner el mínimo al principio de los elementos que quedan por ordenar y el máximo al final. Bueno, vale,... parece que podría ser una buena idea pero en realidad no lo es... si le echamos una pensada nos podemos dar cuenta de que el número de comparaciones e intercambios ¡es el mismo!. Realmente haríamos que cada bucle, el interior y el exterior dieran la mitad de iteraciones... Pero en el bucle exterior meteríamos dos intercambios en lugar de uno y en el interior meteríamos dos comparaciones en lugar de una... es decir... cada bucle hace la mitad de iteraciones pero el doble de trabajo... el resultado: más o menos lo mismo pero con un algoritmo más complicado.

Por otro lado, debido al reducido número de intercambios que realiza el algoritmo, no es posible aprovecharse de una mejora de velocidad en aquellos casos en los que el array esté semi-ordenado o incluso totalmente ordenado. El algoritmo siempre hace las mismas comparaciones e intercambios.


Ultima edición por vic .
Página última modificacion en Viernes 17 de Agosto, 2012 15:11:15 CEST.


¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)

Este sitio web usa cookies para su funcionamiento. Navegar por éste sitio supone la aceptación de la política de cookies -
Política de cookies +