Métodos de ordenación estructura de datos 2 [Intercambio]

Ordenamiento por intercambio

Aquí un vídeo del ordenamiento por intercambio

Clic aquí para descargar el código fuente en C++

Otros métodos:
Información aqui

Métodos de ordenación estructura de datos 2 [Inserción]

Ordenamiento por inserción

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

Explicación de la forma de trabajo del método...

Ejemplo de ordenamiento por inserción ordenando una lista de números aleatorios.

Clic para descargar el código fuente con el método 

Fuente C


Mas información sobre otros métodos

Métodos de ordenación estructura de datos 2 [Burbuja]

Ordenamiento por burbuja (mejorado)

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 necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Este algoritmo es esencialmente un algoritmo de fuerza bruta lógica.

Funcionamiento gráfico del método de ordenación 

Representación animada de ordenación de un conjunto de números mediante el algoritmo burbuja. Comenzando desde el inicio del vector, se compara cada par de elementos adyacentes. Si ambos no están ordenados (el segundo es menor que el primero), se intercambian sus posiciones. En cada iteración, un elemento menos necesita ser evaluados (el último), ya que no hay más elementos a su derecha que necesiten ser comparados, puesto que ya están ordenados.

Nota: Esta es la versión original del burbuja (método de ordenación)

Clic para visualizar el código de trabajo

fuente C++

Visualizar la versión Mejorada del método (Burbuja mejorado)

Visualizar Clic Aquí 

Mas información sobre otros métodos

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