Download - 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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
DIAGRAMA DE FLUJO
PRINCIPAL:
UNMSM 6
Ordenación por Inserción Directa ICIS
INGRESAR:
LISTANORMAL:
LISTADOCOD:UNMSM 7
Ordenación por Inserción Directa ICIS
LISTAEDAD:
UNMSM 8
Ordenación por Inserción Directa ICIS
LISTAPELLIDOS:
UNMSM 9
Ordenación por Inserción Directa ICIS
LISTANOMBRES:
UNMSM 10
Ordenación por Inserción Directa ICIS
PSEUDOCÓDIGOSUNMSM 11
Ordenación por Inserción Directa ICIS
// 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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
UNMSM 16
Ordenación por Inserción Directa ICIS
UNMSM 17
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
//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
Ordenación por Inserción Directa ICIS
} }
} 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
Ordenación por Inserción Directa ICIS
//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
Ordenación por Inserción Directa ICIS
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
Ordenación por Inserción Directa ICIS
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