Ordenamiento por selección

De Wikipedia, la enciclopedia libre

Animación del Selection Sort

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

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lísta
• Intercambiarlo con el primero
• Buscar el 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 seudocó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 la orden intercambiar del final).

[editar] Implementaciones

El algoritmo para Java

public static void selección (int[] v) {
   int min, aux;
 
   for (int i = 0; i < v.length - 1; i++)
   {
      min = i;
      for (int j = i + 1; j < v.length; j++)
      {
         if (v[min] > v[j])
         {
            min = j;
         }
      }
      aux = v[i];
      v[i] = v[min];
      v[min] = aux;
   }
}

El algoritmo para C

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

El algoritmo para 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

El algoritmo para C++

#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;
    }
}

El algoritmo para 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;
    }
}

El algoritmo para Pascal

Procedure SelectionSort(var Sort:Array_integer);
 
var
    a,s,temp:integer;
Begin
 
 For a := 0 to 8 do
  For s := a+1 to 9 do
   If (Sort[a] > Sort[s]) then
    Begin
     temp:= Sort[a];
     Sort[a] := Sort[s];
     Sort[s] := temp;
    End;
 
End;

El algoritmo para 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);
        }
    }
}