1739233 Ordenamiento en C

UNIVERSIDAD CONTINENTAL DE CIENCIAS E INGENIERÍAS

INGENIERÍA INFORMÁTICA
IV SEMESTRE

2007

Métodos de Ordenamiento Codificados
en C++

MÉTODOS DE
ORDENAMIENTO
TÉCNICAS DE PROGRAMACIÓN I

•

DESCRIPCIÓN

•

PROGRAMA COMPLETO DE CADA MÉTODO
o

ORDENACIÓN POR SELECCIÓN

o

ORDENACIÓN POR INSERCIÓN DIRECTA

o

ORDENACIÓN POR INSERCIÓN BINARIA

o

ORDENACIÓN SHELL SORT

o

ORDENACIÓN QUICK SORT

oORDENACIÓN HEAP SORT

GRUPO DE TRABAJO:
SAFORAS CONTRERAS DANNY H.
VELAZCO MENDOZA LUIS.
GUTIERREZ ZUÑIGA CESAR.
CORTIJO PACHECO MIGUEL.
BRAÑEZ ROMÁN SERGIO.
ZARATE ROY

ORDENAMIENTO
Es  la operación  de arreglar los registros  de una tabla en algún orden secuencial  de 
acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal  de un ordenamiento  es el de 
facilitar las búsquedas de los miembros del conjunto ordenado. 
El   ordenar   un  grupo   de   datos   significa   mover   los   datos   o   sus   referencias   para   que 
queden   en   una   secuencia   tal   que   represente   un   orden,   el   cual   puede   ser   numérico, 
alfabético o incluso alfanumérico, ascendente o descendente. 
 1. ORDENAMIENTO POR SELECCIÓN
DESCRIPCIÓN.
•
•
•
•
•

Buscas el elemento más pequeño de la lista. 
Lo intercambias con el elemento ubicado en la primera posición de la lista. 
Buscas el segundo elemento más pequeño de la lista. 
Lo intercambias con el elemento que ocupa la segunda posición en la lista. 
Repites este proceso hasta que hayas ordenado toda la lista. 

ANÁLISIS DEL ALGORITMO.
•
•

Requerimientos  de   Memoria:  Al   igual   que   el   ordenamiento   burbuja,   este 
algoritmo sólo necesita una variable adicional para realizar los intercambios. 
Tiempo de Ejecución:  El ciclo externo se ejecuta  n  veces para una lista de n 
elementos.   Cada   búsqueda   requiere   comparar   todos   los   elementos   no 
clasificados. 

Ventajas: 
•
•
•

Fácil implementación. No requiere memoria adicional. 
Rendimiento constante: poca diferencia entre el peor y el mejor caso. 

Desventajas: 
•
•

Lento. 
Realiza numerosas comparaciones. 

CODIFICACIÓN EN C++
#include
using namespace std;
#include"leearreglo.h"
#define largo 50
void seleccionsort (int A[], int n)
{
int min,i,j,aux;
for (i=0; i {
min=i;
for(j=i+1; j if(A[min] > A[j])
min=j;
aux=A[min];
A[min]=A[i];
A[i]=aux;
}
}
void main ()
{
int A[largo],n;
do{
cout<<"Cantidad de numeros a ingresar: ";cin>>n;
if(n<=0||n>largo)
cout<<"Debe ingresar un valor > a 0 y < a "< }while(n<=0||n>largo);
leeCadena(n,A);
seleccionsort(A,n);
muestraCadena(n,A);
}

2. ORDENAMIENTO POR INSERCIÓN DIRECTA
DESCRIPCIÓN.
El   algoritmo   de   ordenación   por   el   método   de   inserción   directa   es   un  algoritmo 
relativamente   sencillo   y   se   comporta   razonablemente   bien   en   gran   cantidad   de 
situaciones.
Completa   la   tripleta   de   los   algoritmos   de   ordenación   más   básicos   y   de   orden   de 
complejidad cuadrático, junto con SelectionSort y BubbleSort.
Se basa en intentar construir una lista ordenada en el interior del array a ordenar.De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una 
cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene 
un par de características que lo hacen aventajar a los otros dos en la mayor parte de las 
situaciones.
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos 
comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si 
están en orden o no.

•

En cada iteración del ciclo externo los elementos 0 a i forman una lista 
ordenada. 

ANÁLISIS DEL ALGORITMO.
•

•
•

Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por 
lo tanto es estable. 
Requerimientos   de  ...

Leer documento completo

Regístrate para leer el documento completo.