0
Мне нужна помощь. Я реализовал QuickSort в Java, и теперь я тестирую необходимое время для работы с 50.000 до 15.000.000 элементов. Проблема в том, что это так долго. Например:QuickSort в Java, для большого количества элементов
50.000 Elements, 38 seconds.
100.000 Elements, 230 seconds.
250.000 Elements, I'm still waiting (around 8 minutes)
Это нормально? Вот мой код:
/* Clase que implementa el QuickSort */
public class QuickSort {
private static final int corte = 3;
private int i, j;
public void ordenar(Comparable[] a, int izquierda, int derecha) {
if (izquierda + corte <= derecha) {
Comparable pivote = mediana(a, izquierda, derecha);
i = izquierda;
j = derecha - 1;
for (;;) {
while (a[++i].compareTo(pivote) < 0) {
}
while (a[--j].compareTo(pivote) > 0) {
}
if (i < j) {
intercambiar(a, i, j);
} else {
break;
}
intercambiar(a, i, derecha - 1);
}
ordenar(a, izquierda, i - 1);
ordenar(a, i + 1, derecha);
} else {
InsertSort(a);
}
}
private static Comparable mediana(Comparable[] a, int izquierda, int derecha) {
int centro = (izquierda + derecha)/2;
if (a[centro].compareTo(a[izquierda]) < 0) {
intercambiar(a, izquierda, centro);
}
if (a[derecha].compareTo(a[izquierda]) < 0) {
intercambiar(a, izquierda, derecha);
}
if (a[derecha].compareTo(a[centro]) < 0) {
intercambiar(a, centro, derecha);
}
intercambiar(a, centro, derecha - 1);
return a[derecha - 1];
}
private static void intercambiar(Comparable[] arreglo, int a, int b) {
Comparable temporal;
temporal = arreglo[a];
arreglo[a] = arreglo[b];
arreglo[b] = temporal;
}
private void InsertSort(Comparable[] lista) {
for (int i = 1; i < lista.length; i++) {
Comparable auxiliar = lista[i];
int j = i - 1;
while (j >= 0 && lista[j].compareTo(auxiliar) > 0) {
lista[j + 1] = lista[j];
j = j - 1;
}
lista[j + 1] = auxiliar;
}
}
}
public class Test {
public static void main (String [] args) {
long tInicial = 0;
long tFinal = 0;
long tRes = 0;
int tam = 250000;
Arreglo B = new Arreglo (tam);
System.out.print("Prueba de Tiempo:");
B.cargarArreglo();
tInicial = System.currentTimeMillis();
B.ordenarArreglo();
tFinal = System.currentTimeMillis();
tRes = tFinal - tInicial;
System.out.println();
System.out.println("Tiempo Transcurrido (ms): " + tRes + " para " + tam + " elementos.");
}
}
Не 'InsertSort (a);' сортировать весь массив? Почему вы хотите отсортировать весь массив в качестве базового аргумента для рекурсии quicksort? – fabian
Greaaat! Это была моя ошибка! Спасибо! МНОГО! Теперь, 250.000 элементов занимает 328 мс, чтобы закончить. Спасибо дружище :) –