Programación & Unix

Ordenación por Inserción

Algoritmos | October 1st

Este algoritmo se basa en la técnica para ordenar una mano de cartas.

Para cada carta levantada buscamos el lugar correcto y para acomodar la nueva carta debemos hacer espacio en la mano para insertarla.

Análisis

Comenzamos con un “subconjunto ordenado” que contiene solo el primer elemento del conjunto; en este caso es el 8.

Comenzamos tomando el segundo elemento del conjunto y lo comparamos con el elemento del subconjunto. Al ser 5 menor que 8; insertamos el segundo elemento en la primer posición y recorremos el 8 a la segunda posición. Así el subconjunto ordenado tiene dos elementos ordenados (5 y 8).

Ahora tomamos el tercer elemento (2), lo comparamos con el subconjunto. Lo insertamos en la primer posición y recorremos el 5 y el 8. Así el subconjunto ordenado tiene tres elementos (2, 5 y 7).

Luego tomamos el cuarto elemento (7) del conjunto, lo comparamos con el subconjunto. Al ser 7 menor que 8 lo insertamos en la posición en la que se encuentre el 7 y solo recorremos el 8. Ahora el subconjunto ordenado tiene cuatro elementos (2, 5, 7 y 8).

Ahora tomamos el quinto elemento del conjunto (6), lo comparamos con el subconjunto y lo insertamos en la posición del elemento 7 y recorremos el 7 y el 8. Ahora el subconjunto ordenado contiene cinco elementos (2, 5, 6, 7 y 8).

Tomamos el sexto elemento (3), lo comparamos con el subconjunto y lo insertamos en la posición del 5 y recorremos los elementos 5, 6, 7 y 8. Y ahora el subconjunto ordenado tiene seis elementos (2, 3, 5, 6, 7 y 8).

Por ultimo tomamos el séptimo elemento (4), lo comparamos con el subconjunto. Lo insertamos en la posición del número 5 y recorremos los elementos 5, 6, 7 y 8. Y ahora tenemos nuestro arreglo ordenado.

El paso que se encarga de realizar la inserción de los elementos se repite n – 1.

Código de la función

Una vez que hayamos entendido como funciona el método de inserción para ordenar elementos podemos diseñar nuestro código fuente.

void insercion(int array[], int size)
{
	int i, j, valor;

	for (i = 1; i < size; ++i)
	{
		valor = array[i];

		for (j = i; j > 0 && array[j - 1] > valor; --j)
		{
			array[j] = array[j - 1];
		}

		array[j] = valor;
	}
}

Código completo

Pongamos a prueba nuestra función en C++.

#include <iostream>

using namespace std;

void insercion(int array[], int size)
{
	int i, j, valor;

	for (i = 1; i < size; ++i)
	{
		valor = array[i];

		for (j = i; j > 0 && array[j - 1] > valor; --j)
		{
			array[j] = array[j - 1];
		}

		array[j] = valor;
	}
}

int main (int argc, char *argv[])
{
	int numeros[] = {8,5,2,7,6,3,4};

	/* Imprimimos el arreglo original */
	for (int i = 0; i < 7; ++i) {
		cout << numeros[i] << " ";
	}

	cout << endl;

	insercion(numeros, 7);

	/* Imprimimos el arreglo ordenado */
	for (int i = 0; i < 7; ++i){
		cout << numeros[i] << " ";
	}

	cout << endl;
}

$ g++ -o Insercion Insercion.cpp
$ ./Insercion
8 5 2 7 6 3 4
2 3 4 5 6 7 8