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] + " ");
}
}
}