Ordenamiento por inserción directa

"Año de la Integración Nacional y el Reconocimiento de Nuestra

Diversidad"

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOSUniversidad del Perú, Decana de América

Facultad de Ingeniería de Sistemas e InformáticaEAP: Ingeniería de Software

Curso: Introducción a la Computación e Ingeniería de SoftwareProfesor: Luis Guerra Grados.

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

Ordenamiento por Inserción DirectaTrabajo Final de Curso

Integrantes:- Barrantes Cuba Jhon César- Calvo Gordillo Jorge Eduardo- De la Cruz Castro Gustavo Néstor- Luján Vila Frank José

2012

Ordenación por Inserción Directa ICIS

INDICE

INTRODUCCIÓN_______________________________________________________- 3 -

ORDENAMIENTO POR SELECCIÓN DIRECTA__________________________________- 4 -

PROCEDIMIENTO DEL MÉTODO DE ORDENAMIENTO POR INSERCIÓN DIRECTA_____- 5 -

DIAGRAMA DE FLUJO___________________________________________________- 6 -

PRINCIPAL:_______________________________________________________________- 6 -

INGRESAR:________________________________________________________________- 7 -

LISTANORMAL:____________________________________________________________- 7 -

LISTADOCOD:_____________________________________________________________- 8 -

LISTAEDAD:_______________________________________________________________- 9 -

LISTAPELLIDOS:___________________________________________________________- 10 -

LISTANOMBRES:__________________________________________________________- 11 -

PSEUDOCODIGOS_____________________________________________________- 12 -

CODIFICACION EN C++_________________________________________________- 18 -

PRUEBA DEL METODO APLICADO________________________________________- 23 -

CONCLUSIONES______________________________________________________- 24 -

BIBLIOGRAFÍA________________________________________________________- 25 -

UNMSM 2


INTRODUCCIÓN

El ordenamiento es el proceso de reorganización de un conjunto dado de objetos en

una secuencia especificada, el propósito del ordenamiento principal es el de facilitar

búsquedas.

Así, el objetivo de este proyecto es mostrar un método que facilite el ordenamiento

de un grupo de datos según especificaciones del usuario, además se demostrará de

manera lógica y detallada el proceso y funcionamiento de dicho método, incluyendo

un ejemplo que ilustre el método y facilite el entendimiento de este. Así de las

muchas técnica a realizar, presentaremos “El Método de ordenamiento por

Inserción Directa”, conocido también como el método de la baraja. Este método

trata de reorganizar un conjunto dado de objetos en una secuencia especificada, y

cuyo propósito es el de facilitar búsquedas.

UNMSM 3


ORDENAMIENTO POR SELECCIÓN DIRECTA

Este algoritmo es sencillo y se comporta razonablemente en diversas situaciones, además

brinda buenos resultados a efectos practicos, y es el que las personas utilizan generalmente al

ordenar las cartas.

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). En este

punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

Ventajas:

Fácil implementación.

Requerimientos mínimos de memoria

Desventajas:

- En inserción directa: Si observamos la posición del valor que estamos

ordenando se "borra" automáticamente.

UNMSM 4


PROCEDIMIENTO DEL MÉTODO DE ORDENAMIENTO POR INSERCIÓN DIRECTA

1. Partimos de un arreglo aleatoriamente ordenado, y marcamos su primer elemento como parte ordenada, el resto será la parte desordenada.

2. Tomamos el primer elemento de la parte no ordenada, y se almacena en una variable temporal.

3. Comparamos empezando por el final de la parte ordenada, hasta que se encuentra un elemento menor.

4. Se desplaza una posición a la derecha todos los elementos que han resultado mayores que el que queremos insertar y se coloca el valor de la variable temporal en el lugar encontrado.

Se repite el proceso hasta terminar la sección de elementos no ordenados.

UNMSM 5


DIAGRAMA DE FLUJO

PRINCIPAL:

UNMSM 6


INGRESAR:

LISTANORMAL:

LISTADOCOD:UNMSM 7


LISTAEDAD:

UNMSM 8


LISTAPELLIDOS:

UNMSM 9


LISTANOMBRES:

UNMSM 10


PSEUDOCÓDIGOSUNMSM 11


// PROTOTIPO

PROCEDIMIENTO ingresar (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

PROCEDIMIENTO listadocod (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

PROCEDIMIENTO listanormal (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

PROCEDIMIENTO listaedad (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

PROCEDIMIENTO listanombres (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

PROCEDIMIENTO listapellidos (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

// PROGRAMA PRINCIPAL

INICIO entero opción, n, edad[50], código[50], r, jcarácter apellidos[30][30], nombres[30][30]cadena mensajehacer

escribir(“menu”) escribir(“1.- Ingreso de datos: ”)escribir(“2.- Listado normal”) escribir(“3.- Lista ordenada por codigo”)escribir(“4.- Lista ordenada por edades”)escribir(“5.- Lista ordenada por apellidos”)escribir(“6.- Lista ordenada por nombres”)escribir(“7.- Salir”)escribir(“ Seleccione opción: ”)leer(opcion)

caso opción vale`1´: ingresar (código, apellidos, nombres, edad, &n)`2´: listanormal (código, apellidos, nombres, edad, c)`3´: listadocod(código, apellidos, nombres, edad, c)`4´: listaedad(código, apellidos, nombres, edad, c)`5´: listapellidos (código, apellidos, nombres, edad, c)`6´: listanombres (código, apellidos, nombres, edad, c)`7´: mensaje (“Gracias por usar el programa”)Otro: mensaje(“error”)

Mientras(opción<>7)

FIN// PROCEDIMIENTO INGRESO DE DATOS

UNMSM 12


PROCEDIMIENTO ingresar (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

INICIO

Entero i,a Hacer

Escribir(“Numero de alumnos”)Leer(*pn)

Mientras (*pn<1 o *pn>50)Para i de 0 a i<*pn hacer

Escribir(“Codigo”)Leer(código[c])Escribir(“Apellidos”)Leer (apellidos[c])Escribir(“Nombres”)Leer(nombres[c])Escribir(“Edad”) Leer(edad[c])

FparaFIN

//PROCEDIMIENTO LISTA NORMAL

PROCEDIMIENTO listanormal (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

INICIOEntero iEscribir(“Listado de alumnos”)Para i de 0 a i<c hacer

Escribir(“código[i]”, “apellidos[i]”, “nombres[i]”, “edad[i]”)Fpara

FIN

//PROCEDIMIENTO LISTA ORDENADA POR CODIGOS

PROCEDIMIENTO listadocod (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

INICIOEntero i,j,temp

Escribir(“Lista ordenada por codigos”)Para i de 0 a i<c hacerTemp=código[i]

Mientras (j>=0 y temp<código[j]) hacerCódigo[j+1]=código[j--]Código[j+1]=temp

UNMSM 13


FmientrasFpara

Para i de 0 a i<c hacerEscribir(“código[i]”)

FparaFIN

//PROCEDIMIENTO LISTA ORDENADA POR NOMBRES

PROCEDIMIENTO listanombres (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

INICIO

Entero i,jCarácter temp[30]Real comp

Escribir(“Lista ordenada por nombres”)Para i de 0 a i<c hacer

Para j de 0 a j<c hacer Comp=comparación(nombres[j],nombres[j+1])Si (comp>0) entonces

Copiar nombres[j] en tempCopiar nombres[j+1] en nombres[j]Copiar temp en nombres[j+1]

FsiFpara

FparaPara i de 0 a i<c hacer

Escribir(“nombres[i]”)Fpara

FIN

//PROCEDIMIENTO LISTA ORDENADA POR APELLIDOS

PROCEDIMIENTO listapellidos (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

INICIOEntero i,jCarácter temp[30]Real comp

Escribir(“Lista ordenada por apellidos”)Para i de 0 a i<c hacer

Para j de 0 a j<c hacer Comp=comparación(apellidos [j], apellidos [j+1])

UNMSM 14


Si (comp>0) entoncesCopiar apellidos [j] en tempCopiar apellidos [j+1] en apellidos [j]Copiar temp en apellidos [j+1]

FsiFpara

FparaPara i de 0 a i<c hacer

Escribir(“apellidos [i]”)Fpara

FIN

//PROCEDIMIENTO LISTA ORDENADA POR EDADES

PROCEDIMIENTO listaedad (ENTERO codigo[50],CARÁCTER apellidos[30][30], CARÁCTER nombres[30][30], ENTERO edad[50], ENTERO *pn)

INICIO

Entero i,j,temp

Escribir(“Lista ordenada por edades”)Para i de 0 a i<c hacerTemp=edad[i]

Mientras (j>=0 y temp< edad [j]) haceredad [j+1]= edad [j--]edad [j+1]=temp

FmientrasFpara

Para i de 0 a i<c hacerEscribir(“edad[i]”)

Fpara

FIN

PANTALLASUNMSM 15


UNMSM 16


UNMSM 17


CODIFICACION EN C++

#include <cstdlib>#include <iostream>#include <stdio.h>#include <string.h>#include <ctype.h>

using namespace std;int c=0;

void ingresar(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int *pn);void listadocod(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c);void listanormal(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c);void listaedad(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c);void listanombres(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c);void listapellidos(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c);

int main(){ int opcion,n,edad[50],codigo[50],r,j; char apellidos[30][30],nombres[30][30]; //Programa Principal do { cout<<" "<<endl; cout<<" ...:::#::: Programa de Ordenamiento por Insercion Directa :::#::::..."; cout<<" "<<endl; cout<<"\n MENU"; cout<<" "<<endl; cout<<"\n 1. Ingreso de datos: Codigo, Apellidos, Nombres, Edad"; cout<<"\n 2. Listado Normal"; cout<<"\n 3. Lista Ordenada de Codigos"; cout<<"\n 4. Lista Ordenada de Edades"; cout<<"\n 5. Lista Ordenada por Apellidos"; cout<<"\n 6. Lista Ordenada por Nombres"; cout<<"\n 7. Salir"; cout<<" "<<endl; cout<<"\n Seleccione opcion: "; cin>>opcion; switch(opcion) { case 1:ingresar(codigo,apellidos,nombres,edad,&n); cout<<" "<<endl; cout<<" -------------------------------------"<<endl; system("PAUSE"); system("cls"); break;UNMSM 18


case 2:listanormal(codigo,apellidos,nombres,edad,c); cout<<" "<<endl; system("PAUSE"); fflush(stdin); system("cls"); break; case 3:listadocod(codigo,apellidos,nombres,edad,c); cout<<" "<<endl; system("PAUSE"); fflush(stdin); system("cls"); break; case 4:listaedad(codigo,apellidos,nombres,edad,c); cout<<" "<<endl; system("PAUSE"); fflush(stdin); system("cls"); break; case 5:listapellidos(codigo,apellidos,nombres,edad,c); cout<<" "<<endl; system("PAUSE"); fflush(stdin); system("cls"); break; case 6:listanombres(codigo,apellidos,nombres,edad,c); cout<<" "<<endl; system("PAUSE"); fflush(stdin); system("cls"); break; case 7: cout<<" "<<endl; cout<<" Gracias por usar el programa ..."; cout<<" "<<endl; break; default:cout<<" "<<endl; cout<<"Error, pulse 1,2,3,4,5,6 o 7"<<endl; cout<<" "<<endl; system("PAUSE"); fflush(stdin); system("cls"); break; } }while(opcion!=7);

UNMSM 19


cout<<" "<<endl; system("PAUSE"); return EXIT_SUCCESS;}

//Procedimiento Ingreso de datos

void ingresar(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int *pn){int i,a; do{ cout<<"\n Numero de alumnos(Entre 1 y 50): "; cin>>*pn; }while(*pn<1 || *pn>50); for(i=0;i<*pn;i++) { cout<<" -------------------------------------"<<endl; cout<<"\n Codigo (Solo Numeros): "; cin>>codigo[c]; fflush(stdin); cout<<"\n Apellidos: "; cin.getline(apellidos[c],28); cout<<"\n Nombres: "; cin.getline(nombres[c],28); cout<<"\n Edad: "; cin>>edad[c]; c++; }}

//Procedimiento lista normalvoid listanormal(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c){ int i,j,temp; cout<<"\n\n"<<"\t\t\tLISTADO DE ALUMNOS"; cout<<"\n"<<"\t\t\t------------------"; cout<<" "<<endl; cout<<"\n"<<" CODIGO"<<"\t\tAPELLIDOS Y NOMBRES"<<"\t\tEDAD"; for(i=0;i<c;i++) { cout<<"\n"<<codigo[i]<<"\t"<<apellidos[i]<<" "<<nombres[i]<<"\t\t\t"<<edad[i]; } cout<<"\n\n"; c++; return;}

UNMSM 20


//Procedimiento lista ordenada por codigosvoid listadocod(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c){int i,j,temp; cout<<"\n\n"<<"\t\t\tLISTA ORDENADA POR CODIGOS"; cout<<"\n"<<"\t\t\t--------------------------"; cout<<" "<<endl; cout<<"\n"<<" CODIGO"; for(i=0;i<c;i++) { temp=codigo[i]; j=i-1; while(j>=0 && temp<codigo[j]) codigo[j+1]=codigo[j--]; codigo[j+1]=temp; } for(i=0;i<c;i++) { cout<<"\n\t"<<codigo[i]; } cout<<"\n\n"; }

//Procedimiento lista ordenada por nombresvoid listanombres(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c){ int i,j; char temp[30]; float comp; cout<<"\n\n"<<"\t\t\tLISTA ORDENADA POR NOMBRES"; cout<<"\n"<<"\t\t\t--------------------------"; cout<<" "<<endl; cout<<"\n"<<" NOMBRES"; for(i=0;i<c;i++) { for(j=0;j<c-i;j++) { comp = strcmp( nombres[j], nombres[j+1]); if(comp > 0) { strcpy(temp,nombres[j]); strcpy(nombres[j],nombres[j+1]); strcpy(nombres[j+1],temp);

UNMSM 21


} }

} for(i=0;i<c;i++) { cout<<"\n\t"<<nombres[i]; } cout<<"\n\n"; c++; return;

}

//Procedimiento lista ordenada por Apellidosvoid listapellidos(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c){ int i,j; char temp[30]; float comp; cout<<"\n\n"<<"\t\t\tLISTA ORDENADA POR APELLIDOS"; cout<<"\n"<<"\t\t\t----------------------------"; cout<<" "<<endl; cout<<"\n"<<" APELLIDOS"; for(i=0;i<c;i++) { for(j=0;j<c-i;j++) { comp = strcmp(apellidos[j],apellidos[j+1]); if(comp > 0) { strcpy(temp,apellidos[j]); strcpy(apellidos[j],apellidos[j+1]); strcpy(apellidos[j+1],temp); } }

} for(i=0;i<c;i++) { cout<<"\n\t"<<apellidos[i]; } cout<<"\n\n";

}

UNMSM 22


//Procedimiento lista ordenada por edadesvoid listaedad(int codigo[50],char apellidos[30][30],char nombres[30][30],int edad[50],int c){ int i,j,temp; cout<<"\n\n"<<"\t\t\tLISTA ORDENADA POR EDADES"; cout<<"\n"<<"\t\t\t-------------------------"; cout<<" "<<endl; cout<<"\t"<<" EDADES"; for(i=0;i<c;i++) { temp=edad[i]; j=i-1; while(j>=0 && temp<edad[j]) edad[j+1]=edad[j--]; edad[j+1]=temp; } for(i=0;i<c;i++) { cout<<"\n\t"<<edad[i]; } cout<<"\n\n"; c++; return; }

PRUEBA DEL MÉTODO APLICADO

UNMSM 23


CONCLUSIONES

El ordenamiento por inserción directa es práctico y sencillo, se encuentra entre los métodos

más eficientes pues sus operaciones son pocas en comparación con otros métodos. La utilidad

de este programa radica en la capacidad para comprender este método, pues la lógica es

similar a la de cualquier persona al ordenar cartas que encuentre al azar y de forma

desordenada.

Este método es muy útil en la elaboración de arreglos unidimensionales ordenados, pues

permite la ordenación de una manera eficiente y segura, conservando los datos eficazmente.

UNMSM 24


BIBLIOGRAFÍA

http://es.scribd.com/beastieux/d/1739233-Ordenamiento-en-C

http://insercion-binaria.tripod.com/index_files/insercion_directa.htm

http://saforas.wordpress.com/2008/01/06/metodos-de-ordenamiento-hecho-en-c/

http://latecladeescape.com/algoritmos/1123-ordenacion-por-insercion-directa-

http://www.youtube.com/watch?v=brshaFqTEO4&feature=fvwrel

Programación en C++ Edgar Ruiz Lizama

Fundamentos de Programación Luis Joyanes Aguilar

Fundamentos de Programación Ricardo Marcelo Villalobos

UNMSM 25

Documents

Ordenamiento por inserción directa