Algoritmo de ordenamiento por selección

Algoritmo de ordenamiento por selección Concepto: Algoritmo que ubica elementos de una lista o vector, en una secuencia, dada por una relación de orden, tomando como punto de partida el menor elemento.

Algoritmo de ordenamiento por Selección (Selection Sort en inglés): Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenarlo todo. Su implementación requiere O(n2) comparaciones e intercambios para ordenar una secuencia de elementos.

Descripción

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso. Su funcionamiento se puede definir de forma general como:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

Así, se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

para i=1 hasta n-1;

   minimo = i;
   para j=i+1 hasta n
       si lista[j] < lista[minimo] entonces
           minimo = j 
       fin si
   fin para
   intercambiar(lista[i], lista[minimo])

fin para

Ejemplo

El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e']. Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'. Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e']. El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'. El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r']. De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.

Análisis del Costo Computacional

El ciclo externo se ejecuta n veces para una lista de n elementos, o sea que para ordenar un vector de n términos, tiene que realizar siempre el mismo número de comparaciones. c(n)= (n2-n)/2 Cada búsqueda requiere comparar todos los elementos no clasificados, de manera que el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos; por lo que este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad es del orden n2.

Estabilidad, Ventajas y Desventajas

Puede que exista algo de discrepancia en cuanto a si es o no estable este algoritmo, pero en realidad esta implementación parece ser bastante estable. Se puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave. Se vera claramente que el orden relativo entre ellos es conservado. Algunos autores no lo consideran asi, pero independientemente de esto, este algoritmo tienes entre sus ventajas: Es fácil su implementación. No requiere memoria adicional. Realiza pocos intercambios. Tiene un rendimiento constante, pues existe poca diferencia entre el peor y el mejor caso. Como todos también tiene algunas desventajas: Es lento y poco eficiente cuando se usa en listas grandes o medianas. Realiza numerosas comparaciones.

Implementación

A continuación se muestra el Ordenamiento por Selección en algunos de los lenguajes de programación de alto nivel más usados:

Java void selecccion(int[] a) {

       for (int i = 0; i < a.length - 1; i++)
       {
               int min = i;
               for (int j = i + 1; j < a.length; j++)
               {
                       if (a[j] < a[min])
                       {
                               min = j;
                       }
               }
               if (i != min) 
               {
                       int aux= a[i];
                       a[i] = a[min];
                       a[min] = aux;
               }
       }}

C

void ordsel(int * x, int n){

  int minimo=0,i,j;
  int swap;
  for(i=0 ; i<n-1 ; i++)
  {
     minimo=i;
     for(j=i+1 ; j<n ; j++)
        if (x[minimo] > x[j]) 
           minimo=j;
     swap=x[minimo];
     x[minimo]=x[i];
     x[i]=swap;
  }}

Basic For i = 1 To n - 1

  minimo = i
  For j = i + 1 To n
     If x(minimo) > x(j) Then
        minimo = j
     End If
  Next j
  temp = x(i)
  x(i) = x(minimo)
  x(minimo) = tempNext i

C++

1. include <iostream>#include <vector>using namespace std;

template <class T>void ordena_seleccion(vector<T>& v) {
   for (int i = 0; i < v.size() - 1; ++i) {
       int min = i;
       for (int c = i + 1; c < v.size(); ++c) {
           if (v[min] > v[c]) min = c;
       }
       T aux = v[i];
       v[i] = v[min];
       v[min] = aux;
   }}

Perl sub seleccion {

   my $array = shift;    # Recibimos una referencia a un array

   my $i;    # Índice del elemento a comparar
   my $j;    # Índice del valor mínimo a encontrar

   # Para todos los elementos menos el último
   for ( $i = 0; $i < $#$array; $i++ ) {

       # Índice y valor del elemento a comparar
       my ( $m, $x ) = ( $i, $array->[ $m ] );   

       # Buscamos el valor más pequeño de todos los demás
       for ( $j = $i + 1; $j < @$array; $j++ ) {

           ( $m, $x ) = ( $j, $array->[ $j ] )   # Nuevo mínimo encontrado
               if $array->[ $j ] < $x;
       }

       # Hacemos el intercambio de elementos, si es necesario
       @$array[ $m, $i ] = @$array[ $i, $m ]  if $m != $i;
   }}

JavaScript for(var i=0 ; i<vector.length-1 ; i++){

  var menor = i;
  for(var j=i+1 ; j<vector.length ; j++)
  {
     if (vector[menor] > vector[j]) menor = j;
  }
  var temp = vector[menor];
  vector[menor] = vector[i];
  vector[i] = temp;}

PHP function IntercambiarElementos(&$arreglo,$pos1,$pos2){

   $aux=$arreglo[$pos1];
   $arreglo[$pos1]=$arreglo[$pos2];
   $arreglo[$pos2]=$aux;}function PosicionMenorElemento($arreglo,$posinicial){
   $posmenor=$posinicial;
   for($i=$posinicial+1;$i<count($arreglo);$i++){
       if($arreglo[$i]<$arreglo[$posmenor]){
           $posmenor=$i;
       }
   }
   return $posmenor;}function OrdenamientoPorSeleccion(&$arreglo){
   for($i=0;$i<count($arreglo);$i++){
       $posmenor=PosicionMenorElemento($arreglo,$i);
       if($posmenor>$i){
           IntercambiarElementos($arreglo,$i,$posmenor);
       }
   }}

Python def seleccion(lista)

 n = len(lista)

 for i in range(0,n-1):
   k = i
   t = lista[i]
   for j in range(i,n):
     if lista[j] < t:
       k = j
       t = lista[j]
   lista[k] = lista[i]
   lista[i] = t

 return lista

Pascal Procedure OrdSel (var Sec : TipSec; TamSec : Integer);var

  i, j, min, num : Integer;begin
  for i := 1 to TamSec-1 do
  begin
     min := i;
     for j := i+1 to TamSec do
     begin
        NumOpr := NumOpr + 1;
        if Sec[j] < Sec[min] then
           min := j;
     end;
     num := Sec[min];
     Sec[min] := Sec[i];
     Sec[i] := num;
  end;end;

Game Maker Language // array de extensión nfor(i=0 ; i<n-1 ; i+=1){

  menor = i;
  for(j=i+1 ; j<n; j+=1)
  {
     if (vector[menor] > vector[j]) {menor = j;}
  }
  temp = vector[menor];
  vector[menor] = vector[i];
  vector[i] = temp;}

Ver además

• Algoritmo de ordenamiento
• Algoritmo de búsqueda
• Algoritmo de Kruskal
• Algoritmo de Euclides
• Algoritmo de Prim
• Algoritmo de Boruvka
• Algoritmo de Gutmann
• Algoritmo criptográfico
• Algoritmo de Ordenamiento Burbuja
• Algoritmo de Ordenamiento Shell
• Algoritmo genético
• Algoritmo
• Algoritmo de árboles de decisión de Microsoft
• Algoritmo de Búsqueda Heurística A*
• Algoritmo asimétrico

Fuentes

• Aprenda C/C++.
• Estructuras de datos.
• http://es.wikipedia.org