Embed Size (px)
Citation preview
1
INSTITUTO TECNOLOGICO SUPERIOR DE FELIPE
CARRILLO PUERTO
MATERIA:
ESTRUCTURA DE DATOS
DOCENTE:
MIL. NIELS HENRYK ARANDA CUEVAS
UNIDAD 5:
Métodos de ordenamiento
ALUMNO:
ELIEZER BALAM SANTOS
CARRERA:
INGENIERIA EN SISTEMAS COMPUTACIONALES
GRUPO:
B
2
INDRODUCCION:
En esta unidad se entra en la manera de manejo de datos pero no por medio de las maneras vistas anteriormente, sino en una forma de definir la posiciones de los datos por medio de la jerarquía de los datos que se tienen, existen varios métodos para realizarlo de diferentes manera una de las principales es el método burbuja y otros métodos como el quicksort y el método radix, que siempre tienen el mismo propósito de ordenamiento de los datos.
Primer programa de ordenamiento. Método burbuja
#include <iostream>
using namespace std;
void intercambio();
void imprimir();
int Aux;
int i, d;
int A[5];
int main(int argc, char** argv) {
for(i=0; i<5; i++){
cout<<"Ingrese numero: ";
cin>>A[i];
}
for(i=0; i<4; i++){
for(d=i+1; d<5; d++){
3
if(A[d]>A[i]){
intercambio( );
}
}
}
imprimir();
return 0;
}
void intercambio(){
Aux= A[i];
A[i]= A[d];
A[d]= Aux;
}
void imprimir(){
cout<<"\n La secuencia de Mayor a Menor es: ";
for(i=0; i<5; i++){
cout<< A[i];
}
}
4
Descripción del programa:
El programa anterior es un método de ordenamiento de datos con varias funciones que son llamados, como ya sabemos tenemos los códigos principales que ya sabemos utilizar, como lo son los condicionales y los datos abstractos, lo que realizamos es la lectura de los datos que son los números y en base a esos números realizamos el ordenamiento por medio de los apuntadores que se tienen, también podemos interpretarlo si queremos de una manera de árboles.
MÉTODO QUICKSHORT.
#include <iostream>
using namespace std;
void leerarreglo();
void imprimrarre();
void ordenarQuick();
void inter(int x, int y);
int i,j,A[7];
int main(int argc, char *argv[]) {
leerarreglo();
imprimrarre();
ordenarQuick();
imprimrarre();
return 0;
}
void leerarreglo(){
5
for(i=0;i<7;i++){
cout<<"ingrese dato ";
cin>>A[i];
}
}
void imprimrarre(){
for(i=0;i<7;i++){
cout<<A[i]<<" ";
}
cout<<"n";
}
void ordenarQuick(){
int p=6;
i=0;
j=5;
do{
if ((A[i]>A[p])&&(A[j]<A[p])){
inter (i,j);
i++; j--;
}
else {
if (A[i]<A[p])
i++;
if (A[j]>A[p])
j--;
6
}
}while (j>i);
if (A[p]<A[i])
inter (i,p);
}
void inter(int x, int y){
int Aux=A[y];
A[y]=A[x];
A[x]=Aux;
}
Este método realiza el ordenamiento de dato de una manera mas compleja.
METODO RADIX.
#include<iostream>
using namespace std;
#include <math.h>
#define NUMELTS 20
void radixsort(int x[], int n)
{
int front[10], rear[10];
struct {
int info;
int next;
} node[NUMELTS];
7
int exp, first, i, j, k, p, q, y;
/* Inicializar una lista vinculada */
for (i = 0; i < n-1; i++)
{
node[i].info = x[i];
node[i].next = i+1;
} /* fin del for */
node[n-1].info = x[n-1];
node[n-1].next = -1;
first = 0; /* first es la cabeza de la lista vinculada */
for (k = 1; k < 5; k++)
{
/* Suponer que tenemos números de cuatro dígitos */
for (i = 0; i < 10; i++)
{
/*Inicializar colas */
rear[i] = -1;
front[i] = -1;
} /*fin del for */
/* Procesar cada elemento en la lista */
while (first != -1)
{
8
p = first;
first = node[first].next;
y = node[p].info;
/* Extraer el kâsimo dÁgito */
exp = pow(10, k-1); /* elevar 10 a la (k-1)ésima potencia */
j = (y/exp) % 10;
/* Insertar y en queue[j] */
q = rear[j];
if (q == -1)
front[j] = p;
else
node[q].next = p;
rear[j] = p;
} /*fin del while */
/* En este punto, cada registro está en su cola basándose en el dígito k
Ahora formar una lista única de todos los elementos de la cola.
Encontrar el primer elemento. */
for (j = 0; j < 10 && front[j] == -1; j++);
;
first = front[j];
/* Vincular las colas restantes */
while (j <= 9)
{ /* Verificar si se ha terminado */
/*Encontrar el elemento siguiente */
for (i = j+1; i < 10 && front[i] == -1; i++);
9
;
if (i <= 9)
{
p = i;
node[rear[j]].next = front[i];
} /* fin del if */
j = i;
} /* fin del while */
node[rear[p]].next = -1;
} /* fin del for */
/* Copiar de regreso al archivo original */
for (i = 0; i < n; i++)
{
x[i] = node[first].info;
first = node[first].next;
} /*fin del for */
} /* fin de radixsort*/
int main(void)
{
int x[50] = {NULL}, i;
static int n;
cout<<"Cadena de números enteros:\n";
for (n = 0;n<5; n++)
10
{
cin>>x[n];
if(x[n]==-1)
break;
}
if (n)
radixsort (x, n);
for (i = 0; i < n; i++)
cout<<x[i]<<endl;;
return 0;
}
Este método radix es aún más compleja.
CONCLUSION:
Como conclusión tenemos que el uso de estos métodos son importantes para manejar los datos ya que se pueden presentar situaciones donde podemos requerir del uso de cualquiera de las anteriores mencionadas dependiendo de la capacidad de datos que se ingresan en nuestro programa y podemos decir que lo más importante a conocer es el método burbuja. Como hemos dicho anteriormente va ser de gran ayuda para nosotros en nuestra formación academica.
