Stack Overflow en español Asked by IvanRamosO on December 11, 2021
Estaba realizando un Código en el que se necesita comparar 3 algoritmos de ordenamiento: Selección, Inserción y Quicksort para poder saber cuál toma menor tiempo en ejecutarse, en un arreglo de 1000 elementos.
Por teoría el algoritmo Quicksort debería ser más rápido al momento de realizar el ordenamiento de los datos. Pero al ejecutar el programa, el temporizador me arroja que el algoritmo de selección termina siendo mas rápido.
Al principio lo que hago es declarar cada uno de los métodos a comparar. Luego dentro de mi main, llamo a esos métodos y que me muestre el ordenamiento de los datos por pantalla. Luego uso el system nano time para obtener el tiempo, en milisegundos de la ejecución del programa. Para que al final me arroje cuánto se demoró cada uno en ejecutarse.
Necesito ayuda, no se que esté haciendo mal.
Código del Programa:
public class Ordenamiento {
public void selection_sort(int array[])
{
int i , j, menor,pos,tmp;
for(i=0; i< array.length-1;i++){
menor=i;
for (j=i+1;j<array.length;j++){
if (array [j]< array[menor]){
menor =j;
}
}
tmp = array [i];
array [i]=array[menor];
array [menor]=tmp;
}
}
public void Insercion (int array[]){
int pos, aux;
for (int i = 0; i < array.length; i++) {
pos=i;
aux= array[i];
while (pos>0 && array[pos-1]>aux){
array[pos]=array[pos-1];
pos--;
}
array [pos]=aux;
}
}
public void QuickSort (int array [],int primero, int ultimo){
int pivote,aux,i,j;
i=primero;
j=ultimo;
pivote= array[(primero+ultimo)/2];
do{
while (array[i]<pivote ){
i++;
}while (array[j]>pivote){
j--;
}
if(i<=j){
aux=array[i];
array[i]=array[j];
array[j]=aux;
i++;
j--;
}
}while (i<=j);
if(primero< j){
QuickSort( array, primero, j );
}
if (i<ultimo){
QuickSort( array,i,ultimo);
}
}
public static void main(String[] args) {
int[] a= new int [1000];
for (int i = 0; i < 999; i++) {
a[i]=(int) (Math.random() * 999 + 1);
}
Ordenamiento d = new Ordenamiento();
d.selection_sort(a);
System.out.println(Arrays.toString(a));
System.out.println("");
d.Insercion(a);
System.out.println(Arrays.toString(a));
System.out.println("");
d.QuickSort(a, 0, a.length-1);
System.out.println(Arrays.toString(a));
System.out.println("");
long startTime = System.nanoTime();
d.selection_sort(a);
long endTime = System.nanoTime();
System.out.println("Algoritmo de Seleccion: " + (endTime-startTime) + "ms" );
long startTime2 = System.nanoTime();
d.Insercion(a);
long endTime2 = System.nanoTime();
System.out.println("Algoritmo de Inserccion: " + (endTime2-startTime2) + "ms" );
long startTime3 = System.nanoTime();
d.QuickSort(a, 0, a.length-1);
long endTime3 = System.nanoTime();
System.out.println("Algoritmo Quicksort: " + (endTime3-startTime3) + "ms" );
}
Estás llamando a los tres métodos de ordenamiento usando el mismo array (a), lo que pasa es que la primera vez que ordenas el array queda modificado y lo dejas ordenado, por lo que los siguientes llamadas a los diferentes métodos de ordenación parten con ventaja al tener los datos ya ordenados.
Para evitar esto, puedes hacer tres arrays con el mismo contenido y cambiar la lógica de tu código de pruebas a algo así:
public void QuickSort(int array[]) {
QuickSort(array, 0, array.length - 1);
}
public double calcular(int arr[], Consumer<int[]> fun) {
long startTime = System.nanoTime();
fun.accept(arr);
long endTime = System.nanoTime();
return endTime - startTime;
}
public static void main(String[] args) {
long totalA = 0, totalB = 0, totalC = 0;
int[] a = new int[MAX_ELEMENTOS];
int[] b = new int[MAX_ELEMENTOS];
int[] c = new int[MAX_ELEMENTOS];
Random rng = new Random();
Ordenamiento d = new Ordenamiento();
for (int iteracion = 0; iteracion < MAX_ITERACIONES; iteracion++) {
for (int i = 0; i < MAX_ELEMENTOS; i++) {
int val = rng.nextInt(MAX_VALORES);
a[i] = b[i] = c[i] = val;
}
totalA += d.calcular(a, arr -> d.selection_sort(arr));
totalB += d.calcular(b, arr -> d.Insercion(arr));
totalC += d.calcular(c, arr -> d.QuickSort(arr));
}
System.out.println("Media selección: " + totalA / MAX_ITERACIONES);
System.out.println("Media inserción: " + totalB / MAX_ITERACIONES);
System.out.println("Media quicksort: " + totalC / MAX_ITERACIONES);
}
Fíjate que he hecho lo siguiente:
Sobrecargar el método QuickSort para que se llame de la misma forma que el resto de los otros métodos de ordenación y no sea necesario pasarle el índice de origen y la longitud del array.
Definir un método calcular que reciba un array de números y la función de ordenación que queremos probar. En este caso se ha usado un Consumer, es decir, una función que admite un parámetro y no devuelve nada.
Usar el método nextInt de la clase Random para evitar casting innecesarios.
Crear una variable total para cada uno de los métodos de ordenación, esto nos servirá para calcular el total.
Se ha sacado a constantes el máximo de elementos del array, el máximo de iteraciones a procesar para obtener la media, y el máximo de los valores que pueden ir dentro del array para evitar el uso de números mágicos
El cálculo del tiempo se hace llamando a la función calcular a la que le pasamos como parámetros el array de números y una función lambda en la que se llama a la función de ordenación que queremos probar, el resultado se añade a los totales correspondientes.
Al final de las iteraciones se calcula la media dividiendo el total de los tiempos entre el número de iteraciones hechas.
Poniendo 1000 como valor a todas las constantes, yo obtengo tiempos como estos:
Media selección: 552158
Media inserción: 159388
Media quicksort: 83111
Donde se ve que quicksort hace honor a su nombre y demuestra que es el más rápido de todos.
EDIT: Como bien dice @gbianchi, efectivamente hacer una prueba con un único set de datos nos puede llevar a resultados inesperados. Lo suyo es hacer pruebas con múltiples sets, y múltiples iteraciones.
EDIT2: He cambiado el código para que calcule la media y he organizado un poco el código para evitar números mágicos y minimizar el código duplicado.
Más info:
Answered by ordago on December 11, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP