По мотивам поста - завал java.util.Arrays.sort()
Я попробовал скормить данный int массив Arrays.sort() и ужаснулся - программа реально долго работает.
Но неужели всё так печально?
Оказалось - не совсем.
Далее для простоты привожу исходные коды методов, которые я использовал для проведения собственных "расследований".
Чтение в первых двух случаях шло из файла, который сгенерировал скрипт-убийца.
Последние 2 метода используют массив с рандомным заполнением. Для чистоты эксперимента, так сказать.
void solve() {
int ar[] = new int[500000];
for (int i = 0; i <ar.length; i++){
ar[i] = in.nextInt();
}
out.println("Start sorting");
out.flush();
long start = System.currentTimeMillis();
Arrays.sort(ar);
long total = System.currentTimeMillis()-start;
out.println("Sorted at "+total);
}
Sorted at 123324
void solve() {
Integer ar[] = new Integer[500000];
for (int i = 0; i <ar.length; i++){
ar[i] = in.nextInt();
}
out.println("Start sorting");
out.flush();
long start = System.currentTimeMillis();
Arrays.sort(ar);
long total = System.currentTimeMillis()-start;
out.println("Sorted at "+total);
}
Start sortingSorted at 530
void solve() {
Random r = new Random();
Integer ar[] = new Integer[500000];
for (int i = 0; i <ar.length; i++){
ar[i] = r.nextInt();
}
out.println("Start sorting");
out.flush();
long start = System.currentTimeMillis();
Arrays.sort(ar);
long total = System.currentTimeMillis()-start;
out.println("Sorted at "+total);
}
Start sortingSorted at 624
void solve() {
Random r = new Random();
int ar[] = new int[500000];
for (int i = 0; i <ar.length; i++){
ar[i] = r.nextInt();
}
out.println("Start sorting");
out.flush();
long start = System.currentTimeMillis();
Arrays.sort(ar);
long total = System.currentTimeMillis()-start;
out.println("Sorted at "+total);
}
Start sortingSorted at 234
Как видно - не всё так и страшно.
Если использовать Integer[] вместо int[] - будет использоваться сортировка слиянием, не имеющая худшего случая вообще (как и лучшего).
Комментарии (14)
+1
