martes, 16 de febrero de 2010
Ordenación por Inserción
Ordenación por Inserción
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.
#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;
}
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario