У меня есть следующие алгоритмы сортировки сортировки, сортировки сортировки и быстрого сортировки соответственно. Я выполнил тест, сортируя массив из 10 000 целых чисел от 0 до 1000 10 раз для каждого алгоритма. Любопытно, что среднее значение для сортировки сортировки значительно ниже, чем сортировка вставки и быстрая сортировка. Средние значения составляли 182044,4, 217,9 и 545,4 миллисекунды для вставки, отбора и быстрого сортировки соответственно. Учитывая тот факт, что я, скорее всего, сделаю небольшие улучшения для вставки и быстрого сортировки, я бы не ожидал, что отсутствие этих улучшений приведет к таким большим различиям. Где я ошибаюсь в реализации здесь? Опять же, небольшие улучшения, такие как перемещение индексов или проверок, но фактические ошибки.Почему сортировка сортировки лучше, чем вставка И быстрая сортировка
я предоставил код для испытаний и результаты ниже
Благодаря
public final static <E extends Comparable<E>> ArrayList<E> insertionSort(ArrayList<E> arr)
{
for(int i = 1; i < arr.size(); i++)
{
for(int j = i; j > 0; j--)
{
if(arr.get(j).compareTo(arr.get(j - 1)) < 0)
{
swap(arr, j, j-1);
}else{
break;
}
}
}
return arr;
}
`
public final static <E extends Comparable<E>> ArrayList<E> selectionSort(ArrayList<E> arr)
{
for(int i = 0; i < arr.size() - 1; i++){
int min = i;
for(int j = i + 1; j < arr.size(); j++){
if(arr.get(j).compareTo(arr.get(min)) < 0){
min = j;
}
}
swap(arr, i, min);
}
return arr;
}`
`
public final static <E extends Comparable<E>> ArrayList<E> quickSort(ArrayList<E> arr)
{
quickSort(arr, 0, arr.size() -1);
return arr;
}
private static <E extends Comparable<E>> void quickSort(ArrayList<E> arr, int lo, int hi)
{
if(hi - lo < 1)
{
return;
}
if((hi - lo) == 1)
{
if(arr.get(lo).compareTo(arr.get(hi)) > 0)
{
swap(arr, lo, hi);
}
return;
}
int pivot = (hi - lo)/2 + lo;
int j;
swap(arr, pivot, hi);
pivot = hi;
for(int i = lo; i < pivot; i++)
{
if(arr.get(i).compareTo(arr.get(pivot)) > 0)
{
for(j = i + 1; j < pivot; j++)
{
if(arr.get(j).compareTo(arr.get(pivot)) < 0)
{
swap(arr, i, j);
break;
}
}
if(j == pivot)
{
swap(arr, i, pivot);
pivot = i;
}
}
}
//do sort op here
quickSort(arr, lo, pivot - 1);
quickSort(arr, pivot + 1, hi);
}
`
Код для проверки - genRans (n) только генерирует список массивов случайных чисел между 0 и n ` int n = 10000; ArrayList list = new ArrayList();
int tries = 10;
double[] times = new double[tries];
double sum = 0;
double time = 0;
long startTime = 0;
long endTime = 0;
for(int i = 0; i < tries; i++)
{
list = genRans(n);
startTime = System.nanoTime();
//System.out.println("before " + list);
Sort.selectionSort(list);
//System.out.println("after" + list);
endTime = System.nanoTime();
time = (endTime - startTime)/1000000;
times[i] = time;
sum += time;
}
System.out.println("Times for selection sort = " + Arrays.toString(times));
System.out.println("Avg time for selection = " + sum/tries);
sum = 0;
for(int i = 0; i < tries; i++)
{
list = genRans(n);
startTime = System.nanoTime();
Sort.insertionSort(list);
endTime = System.nanoTime();
time = (endTime - startTime)/1000000;
times[i] = time;
sum += time;
}
System.out.println("Times for insertion sort = " + Arrays.toString(times));
System.out.println("Avg time for insertion = " + sum/tries);
sum = 0;
for(int i = 0; i < tries; i++)
{
list = genRans(n);
startTime = System.nanoTime();
Sort.quickSort(list);
endTime = System.nanoTime();
time = (endTime - startTime)/1000000;
times[i] = time;
sum += time;
}
System.out.println("Times for quick sort = " + Arrays.toString(times));
System.out.println("Avg time for quick = " + sum/tries);
}
` Результаты: Времена для выбора рода = [235,0, 214,0, 216,0, 216,0, 216,0, 216,0, 217,0, 216,0, 217,0, 216,0] Среднее время для выбора = 217,9 Времена для вставки рода = [182936,0, 181976,0, 182571,0, 182448,0, 180757,0, 180567,0, 181593,0, 185073,0, 181241,0, 181282,0] Среднее время для ввода = 182044,4 Времена для быстрой сортировки = [629,0, 487,0, 579,0, 557,0, 547,0, 482,0, 543,0, 571,0, 525,0, 534,0] Среднее время для быстрого = 545,4
Я думаю, проблема заключается в том, как вы измеряете результат выполнения вашей программы. Позвольте мне угадать: внутри 'main', вы вызываете каждый метод сортировки один за другим. –
Просьба указать код, который вы используете для проверки производительности. – StriplingWarrior
Предоставлено в редакции – user3442536