Método de selección en C++

 Consiste en lo siguiente:

• Buscas el elemento más pequeño de la lista.
• Lo intercambias con el elemento ubicado en la primera posición de la lista.
• Buscas el segundo elemento más pequeño de la lista.
• Lo intercambias con el elemento que ocupa la segunda posición en la lista.
• Repites este proceso hasta que hayas ordenado toda la lista.

Pseudocódigo en C++

for (i=0; i<TAM - 1; i++)

pos_men = Menor(lista, i);

temp = lista[i];

lista[i] = lista [pos_men];

lista [pos_men] = temp;

Nota: Menor(lista, i) es una función que busca el menor elemento entre las posiciones i y TAM-1. 

Ejemplo:

Vamos a ordenar la siguiente lista (la misma del ejemplo anterior):

4 - 3 - 5 - 2 - 1

Comenzamos buscando el elemento menor entre la primera y última posición. Es el 1. Lo intercambiamos con el 4 y la lista queda así:

1 - 3 - 5 - 2 - 4

Ahora buscamos el menor elemento entre la segunda y la última posición. Es el 2. Lo intercambiamos con el elemento en la segunda posición, es decir el 3. La lista queda así:

1 - 2 - 5 - 3 - 4

Buscamos el menor elemento entre la tercera posición y la última. Es el 3, que intercambiamos con el 5:

1 - 2 - 3 - 5 - 4

El menor elemento entre la cuarta y quinta posición es el 4, que intercambiamos con el 5:

1 - 2 - 3 - 4 - 5

Código en C++

#include <iostream>

#include <time.h>//librería ara usar random

#define TAM 10 //se define una variable global

 

int main()

{

    //declaración de las variables a utilizar

    //  temp:para almacenar temporalmente un número

    //  lista:los elementos a ordenar

    //  TAM:tamaño de la lista

    // i, j:para usarse en los ciclos

    int temp, i, j;

    int lista[TAM];

    srand(time(NULL));

    //llenar vector con valores aleatorios

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

    {

        lista[i] = rand() % 100;//generación de números aleatorios

    }

 

    //imprimir arreglo desordenado, \n para el salto de línea

    printf("Vector desordenado\n");

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

    {

        printf("%d\t", lista[i]);//\t da la tabulación o con \n para salto de línea

    }

 

    //ciclos anidados para ordenar los elementos con inserción

    for (i = 1; i < TAM; i++)

    {

        temp = lista[i];//se almacena el número en temp

        j = i - 1;//asignamos a j el valor de i menos 1 para comparar con el elemento anterior

        while ((lista[j] > temp) && (j >= 0))//mientras los elementos sean mayores a temp y todavía tengamos elementos

        {

            lista[j + 1] = lista[j];//al ser mayor lo almacenamos en la posición j+1

            j--;//decrementamos j

            lista[j + 1] = temp;//almacenamos temporal en j+1

        }

    }

 

    //imprimir vector ordenado

    printf("\n");

    printf("Vector ordenado\n");

    for (int i = 0; i < TAM; i++)

    {

        printf("%d\t", lista[i]);//\t da la tabulación o con \n para salto de línea

 

    }

 

    //detener la pantalla pidiendo un caracter de entrada

    int flag = getchar();

}

 

Ventajas:

• Fácil implementación.
• Requerimientos mínimos de memoria.

Desventajas:

• Lento.
• Realiza numerosas comparaciones.

Método burbuja en C++

 

Descripción

Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. 

Pseudocódigo en C++

for (i=1; i<TAM; i++)

    for j=0 ; j<TAM - 1; j++)

if (lista[j] > lista[j+1])

temp = lista[j];

lista[j] = lista[j+1];

lista[j+1] = temp;

Ejemplo

Tenemos la siguiente lista:

4 - 3 - 5 - 2 - 1

Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos:

3 - 4 - 5 - 2 - 1

Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos:

3 - 4 - 2 - 5 - 1

Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente:

3 - 4 - 2 - 1 - 5

Repitiendo este proceso vamos obteniendo los siguientes resultados:

3 - 2 - 1 - 4 - 5

2 - 1 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

Código

#include <iostream>

#include <time.h>//librería ara usar random

#define TAM 10 //se define una variable global

using namespace std;//para usar strings

 

int main()

{

    //declaración de las variables a utilizar

    //  temp:para almacenar temporalmente un número

    //  lista:los elementos a ordenar

    //  TAM:tamaño de la lista

    int temp;

    int lista[TAM];

    srand(time(NULL));

    //llenar vector con valores aleatorios

    for (int i = 0; i < TAM; i++)

    {

        lista[i]=rand()%100;//generación de números aleatorios

    }

 

    //imprimir arreglo desordenado, \n para el salto de línea

    printf("Vector desordenado\n");

    for (int i = 0; i < TAM; i++)

    {

        printf("%d\t", lista[i]);//\t da la tabulación o con \n para salto de línea

    }

 

    //ciclos anidados para ordenar los elementos con método burbuja

    for (int i = 1; i < TAM; i++)

    {

        for (int j = 0; j < TAM - 1; j++)

        {

            if (lista[j] > lista[j + 1])//se compara el elemento actual con el elemento siguiente

            {

                temp = lista[j];//se almacena temporalmente el elemento actual

                lista[j] = lista[j + 1];//al elemento actual lo reemplazamos por el siguiente

                lista[j + 1] = temp;//reemplazamos al elemento siguiente por el elemento almacenado en el valor temporal

            }

        }

    }

 

    //imprimir vector ordenado

    printf("\n");

    printf("Vector ordenado\n");

    for (int i = 0; i < TAM; i++)

    {

        printf("%d\t", lista[i]);//\t da la tabulación o con \n para salto de línea

 

    }

 

    //detener la pantalla pidiendo un caracter de entrada

    int flag = getchar();

}

Ventajas:

Fácil implementación.

No requiere memoria adicional.

Desventajas:

Muy lento.

Realiza numerosas comparaciones.

Realiza numerosos intercambios.