Métodos de ordenamiento Estructura de datos 2 [ISelección]

Método de 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.

Acá se presenta un ejemplo de como el método ordena.

Descripción del algoritmo:

Básicamente hace lo 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, desde la posición i:

para i=1 hasta n-1

    mínimo = i;

    para j=i+1 hasta n

        si lista[j] < lista[mínimo] entonces

            mínimo = j /* (!) */

        fin si

    fin para

    intercambiar(lista[i], lista[mínimo])

fin para

---------------------------------------------------------------------

Codificación en C++

#include <stdio.h>

#include <iostream.h>

#include <conio.h>

#define N 100

void ordSeleccion (long a[], int n);

void entradaLista (long a[], int n);

void imprimirLista (long a[], int n);

int comp=0,intercambios=0;

int main()

{

int n;

long v[N];

do {

printf("\nIntroduzca el número de elementos: ");

scanf("%d", &n);

} while ((n < 1) && (n > N));

entradaLista(v, n);

/* muestra lista original */

printf("\nLista original de %d elementos", n);

imprimirLista(v, n);

/* ordenación ascendente de la lista */

ordSeleccion(v, n);

printf("\nLista ordenada de %d elementos", n);

imprimirLista(v, n);

cout<<"\nel numero de comparaciones es "<<comp;

cout<<"\nel numero de intercambios es "<<intercambios;

getch();

return 0;

}

void ordSeleccion (long a[], int n) {

 int indiceMenor, i, j; /* ordenar a[0]..a[n-2] y a[n-1] en cada pasada */

 for (i = 0; i < n-1; i++) { /* comienzo de la exploración eníndice i */

 indiceMenor = i; /* j explora la sublista a[i+1]..a[n-1] */

 for (j = i+1; j < n; j++) {

 comp++;

 if (a[j] < a[indiceMenor])

   indiceMenor = j;

 /* sitúa el elemento más pequeño en a[i] */

    }

 if (i != indiceMenor) {

    double aux = a[i];

   a[i] = a[indiceMenor];

    a[indiceMenor] = aux ;

     intercambios++;

    }

    }

    }

//El análisis del algorit

void imprimirLista (long a[], int n)

{

int i;

for (i = 0 ; i < n ; i++)

{

char c;

c = (i%10==0)?'\n':' ';

printf("%c%d", c, a[i]);

}

}

void entradaLista (long a[], int n)

{

int i;

printf("\n Entrada de los elementos\n");

for (i = 0 ; i < n ; i++)

{

printf("a[%d] = ");

scanf("%d", a+i);

}

}

Descargar Archivo .txt del código...

clic aquí para descargar 

Mas información sobre otros métodos