Ordenamiento por selección

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.

Descripción del algoritmo

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 0:

para i=0 hasta n-2
    mínimo = i;
    para j=i+1 hasta n-1
        si lista[j] < lista[mínimo] entonces
            mínimo = j /* (!) */
        fin si
    fin para
    intercambiar(lista[i], lista[mínimo])
fin para

Ejemplo del algoritmo en C++

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

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, sino 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[mínimo])

siempre se ejecuta, aun cuando i= mínimo, 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 número de intercambios es lineal, del orden de n.

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

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

Ejemplo

C++

#include<iostream>

void seleccion(int longitud,int* array);
void imprimir(int longitud,int* array);

int main()
{
    int longi;
    std::cin>> longi;
    int* array = new int [longi];
    for (int i = 0; i < longi; i++)
    {
        std::cin>>array[i];
    }
    
    
    seleccion(longi, array);
   
    delete[] array;
    return 0;
}

void seleccion(int longitud, int* array){
    int menor;
    int aux;
    for (int i = 0; i < longitud - 1; i++) 
    {
        menor = i;
        for (int j = i + 1; j < longitud; j++)
        {
            if (array[j] < array[menor])
            {
                menor = j;
            }
        }
        aux = array[i];
        array[i] = array[menor];
        array[menor] = aux;
        
        std::cout<<std::endl;
        imprimir(longitud, array);
    }
}

void imprimir(int longitud,int* array){
    for (int k = 0; k < longitud; k++)
        {
            std::cout<< array[k]<<" ";
        }
}

Véase también

Algoritmo de ordenamiento

Enlaces externos

Datos: Q220831
Multimedia: Selection sort / Q220831