Ordenamiento por selección

Animación del Selection Sort

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O$(n^2)$ operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista
• Intercambiarlo con el primero
• Buscar el siguiente mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:

• 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

De esta manera 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

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 intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar(lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando el orden intercambiar del final).

Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.

Rendimiento del algoritmo

Al algoritmo de ordenamiento por selección, para ordenar un vector de n términos, tiene que realizar siempre el mismo número de comparaciones:

$c(n) = \cfrac{n^2-n}{2}$

Esto es, el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos.

$\Theta (c(n))= n^2 \;$

Por lo tanto la cota ajustada asintótica del número de comparaciones pertenece al orden de n cuadrado.

El número de intercambios i(n), también es fijo, téngase en cuenta que la instrucción:

intercambiar(lista[i], lista[minimo])

siempre se ejecuta, aun cuando i= minimo, lo que da lugar:

$i (n) = n \;$

sea cual sea el vector, y el orden de sus términos, lo que implica en todos los casos un coste lineal:

$\Theta (i(n))= n \;$

la cota ajustada asintótica del numero de intercambios es lineal, del orden de n.

Asimismo, la formula que representa el rendimiento del algoritmo, viene dada por la función:

$c(n) = \cfrac{n^2+n}{2}$

Implementaciones

• Java

/*Algoritmo Recursivo
* Llamada
* int j=1, i=0;
* Ordenamientos.ordenSeleccionRecursivo(vector, i,j, menor);
*/
public abstract class Ordenamientos{
 
public static void ordenSeleccionRecursivo(int [] vector, int i, int j, int menor){
        int aux;
        if(i==vector.length-1)
            return;
        if(j==vector.length)            
            j=i+1;
        if(vector[menor]>vector[j])
            menor=j;
        if(j==vector.length -1 && i<vector.length){
            aux = vector[i];
            vector[i] = vector[menor];
            vector[menor] = aux;
            menor=++i;
        }
        ordenSeleccionRecursivo(vector, i, j+1 ,menor);
}
 
public static 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 min,i,j,aux,ban;
 
   for(i=0 ; i<n-1 ; i++)
   {
      ban=0;
      min=i;//min es el elemento primero de la sublista
      for(j=i+1 ; j<n ; j++){//Esta es la sublista.
         if (x[min] > x[j]){ 
            min=j;//min ahora apunta a el elemento menor de la sublista
            ban=1;//seteamos ban a 1 para que efectue el intercambio dentro de la sublista
         }
      }
      if(ban){
      aux=x[min];
      x[min]=x[i];
      x[i]=aux;
      }
   }
}

• 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) = temp
Next i

• C++

#include <iostream>
#include <vector>
using namespace std;
 
 
template <class T>
void ordena_seleccion(vector<T>& v) {
    for (int i = 0; i < v.size(); ++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;
    }
}

• Ruby

def selection_sort(array)
 
    for i in 0...array.size
      min = i
      for k in i+1...array.size
        if( array[k]<array[min] )
          min = k
        end
      end
      if( min != i )
        temp = array[i]
        array[i] = array[min]
        array[min] = temp
      end
    end
    array
  end

• 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
         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 n
for(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;
}