Embed Size (px)
DESCRIPTION
Comparación de los diferentes métodos de ordenamiento asi como el codigo fuente del programa creado en el IDE NETBEANS con el cual se realizo dicha comparacion, este funciona con un Array de 100 numeros aleratorios.
Citation preview
Estructura De Datos Trabajo Final Página 1
INSTITUTO TECNOLÓGICO DE CD. VICTORIA
INGENIERÍA EN SISTEMAS
COMPUTACIONALES
UNIDAD ACADEMICA DE ABASOLO TAMAULIPAS
MATERIA: Estructura De Datos
ACTIVIDAD: Trabajo Final U5.
ASESOR: JESUS EMMANUEL HERNANDEZ ARANDA.
ALUMNOS:
Julio Cesar Resendiz Ramírez 11380876
Oscar Abelino Pérez Montoya 10380893
Karla Liliana Hinojosa Figueroa 09380094
Abasolo Tamaulipas a 18 de Junio del 2012.
Estructura De Datos Trabajo Final Página 2
METODO DE ORDENAMIENTO
CANTIDAD DE ELEMENTOS
TOTAL DE TIEMPO DE EJECUCION (SEGUNDOS)
COMPARACIONES Y COMENTARIOS
Burbuja
100 1. 0 2. 0 3. 0 4. 0 5. 0
Al realizar la ejecución de los métodos 5 veces se observó que es eficiente.
QuickSort
100 1. 0 2. 0 3. 0 4. 0 5. 0
Al realizar la ejecución se observó que el método es eficiente al igual que método burbuja.
Shell Sort
100 1. 0 2. 0 3. 0 4. 0 5. 0
Se observó que el método es similar al método burbuja y quick short.
Radix
100 1. 5 2. 1 3. 0 4. 1 5. 0
Se puede observar que al ejecutar el Radix es menos eficiente que a los 3 métodos pasados, ya que el tiempo de ejecución es mayor.
Estructura De Datos Trabajo Final Página 3
//Julio Cesar Resendiz Ramirez
//Oscar Abelino Perez Montoya
//Karla Liliana Hinojosa Figueroa
package edd_trabajo.pkgfinal.u5;
public class EdD_TrabajoFinalU5 {
void burbuja(int[] arr, int n){
int temporal;
for(int i=0; i<n-1 ; i++ ) {
for(int j=i+1 ; j< n ; j++) {
if(arr[j]<arr[i]){
temporal = arr[j];
arr[j] = arr[i];
arr[i] = temporal;
}
}
}
}
void radixSort(int[] arr){
if(arr.length == 0) {
return;
}
int[][] np = new int[arr.length][2];
int[] q = new int[0x100];
int i,j,k,l,f = 0;
Estructura De Datos Trabajo Final Página 4
for(k=0;k<4;k++){
for(i=0;i<(np.length-1);i++) {
np[i][1] = i+1;
}
np[i][1] = -1;
for(i=0;i<q.length;i++) {
q[i] = -1;
}
for(f=i=0;i<arr.length;i++){
j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
if(q[j] == -1) {
l = q[j] = f;
}
else{
l = q[j];
while(np[l][1] != -1) {
l = np[l][1];
}
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
}
Estructura De Datos Trabajo Final Página 5
}
void shellSort( int vec []) {
for( int p = vec.length / 2; p > 0; p = p == 2 ? 1 : (int) ( p / 2.2 ) ) {
for( int i = p; i < vec.length; i++) {
int tmp = vec[i];
int j;
for(j = i; j >= p && tmp < vec[j - p]; j -= p ) {
vec[j] = vec[j - p];
}
vec[j] = tmp;
}
}
}
void quicksort(int[] v) {
final int N = v.length;
quickSort(v,0,N-1);
}
public static void quickSort(int[] v, int inicio, int fin) {
if(inicio>=fin) return ;
int pivote = v[inicio];
int izq = inicio+1;
int der = fin;
while(izq<=der) {
while(izq<=fin && v[izq]< pivote) izq++;
while(der>inicio && v[der]>=pivote) der--;
if(izq<der) {
Estructura De Datos Trabajo Final Página 6
int tmp = v[izq];
v[izq] = v[der];
v[der] = tmp;
}
}
if(der>inicio) {
int tmp = v[inicio];
v[inicio]= v[der];
v[der] = tmp;
}
quickSort(v,inicio, der-1);
quickSort(v, der+1, fin);
}
public static void main(String[] args) {
int i;
int primero;
int v[]=new int[100];
for(primero=0;primero<100;primero=primero+1) {
v[primero]=(int) ((100-1)*Math.random()+primero);
}
for(primero=0;primero<100;primero=primero+1);
EdD_TrabajoFinalU5 Joy=new EdD_TrabajoFinalU5();
long B1 = System.currentTimeMillis();
Joy.burbuja(v,primero);
long B2= System.currentTimeMillis();
System.out.println ("\n El metodo de la Burbuja ha tardado " + (B2-B1) + " segundos \n");
Estructura De Datos Trabajo Final Página 7
System.out.print("Metodo de la Burbuja \n");
for(i=0;i<v.length;i++) {
System.out.print(v[i] + " ");
}
long S1 = System.currentTimeMillis();
Joy.shellSort(v);
long S2= System.currentTimeMillis();
System.out.println ("\n\nEl metodo de SellSort ha tardado " + (S2-S1) + " segundos \n");
System.out.print("Metodo de la shellsort \n");
for(i=0;i<v.length;i++) {
System.out.print(v[i] + " ");
}
long R1 = System.currentTimeMillis();
Joy.radixSort(v);
long R2= System.currentTimeMillis();
System.out.println ("\n\nEl metodo de RadixSort ha tardado " + (R2-R1) + " segundos \n");
System.out.print("Metodo de la radixsort \n");
for(i=0;i<v.length;i++) {
System.out.print(v[i] + " ");
}
long Q1 = System.currentTimeMillis();
Joy.quicksort(v);
long Q2= System.currentTimeMillis();
System.out.println ("\n\nEl metodo de quicksort ha tardado " + (Q2-Q1) + " segundos \n");
System.out.print("Metodo de la quicksort \n");
for(i=0;i<v.length;i++) {
Estructura De Datos Trabajo Final Página 8
System.out.print(v[i] + " ");
}
}
}
