Ordenamiento por selección

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(n2) 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 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

Artículo principal: Cota ajustada asintótica

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.

Implementaciones

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


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);
        }
    }
}
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
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;
// 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;
}

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Ordenamiento por selección — El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O operaciones para ordenar una lista de n elementos. Su funcionamiento es el siguiente: ● Buscar el mínimo elemento de la lísta ● Intercambiarlo …   Enciclopedia Universal

  • Ordenamiento — puede referise a: En derecho: Ordenamiento jurídico, el conjunto de normas globales que rigen en una determinada época y en un lugar determinado. Ordenamiento jurídico de la Orden de Malta, el Ordenamiento jurídico especial de la Orden de Malta.… …   Wikipedia Español

  • Ordenamiento de burbuja — La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es… …   Wikipedia Español

  • Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por …   Wikipedia Español

  • Ministerio de Vivienda, Ordenamiento Territorial y Medio Ambiente de Uruguay — Ministerio de Vivienda, Ordenamiento Territorial y Medio Ambiente …   Wikipedia Español

  • Darwinismo — Charles Darwin en 1880, con 71 años, dos antes de su muerte. La repercusión de la teoría de la evolución por selección natural aparecida en 1859 con la publicación de El origen de las especies ya era una realidad que revolucionó numerosos campos… …   Wikipedia Español

  • Venezuela — Para otros usos de este término, véase Venezuela (desambiguación). República Bolivariana de Venezuela …   Wikipedia Español

  • Montículo suave — Para otros usos de este término, véase Montículo (desambiguación). En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper… …   Wikipedia Español

  • Orden — Este artículo trata sobre el concepto de orden. Para otros usos de este término, véase Orden (desambiguación). Uno de los significados de orden es la propiedad que emerge en el momento en que varios sistemas abiertos, pero en origen aislados,… …   Wikipedia Español

  • Origen de las aves — Un modelo de Archaeopteryx lithographica en exhibición en el Museo de Historia Natural de la Universidad de Oxford. El origen de las aves ha sido un asunto contencioso dentro de la biología evolutiva por muchos años, pero más recientemente ha… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”