alex-rogov
commented
5 years ago Insertion sort работает быстрее чем merge sort в случае с небольшими массивами. В ниже приведенном примере я заметил, что при заполнении массива случайными числами, и используя threshold (в данном случае значение, ниже которого выполняется сортировка вставкой) в диапазоне 16 – 64 сортировка вставкой проявила себя примерно в два раза быстрее, чем merge sort.
Разница становится заметней при увеличении изначально заданного массива чисел в размере. В программе я реализовал гибридную сортировка. Ее нельзя назвать стабильной сортировкой, ведь порядок одинаковых элементов может не сохраниться из-за перестановки во время выполнения merge сортировки.
При использовании массива в 500 000 целых чисел сортировка занимает около 1/8 секунды. Для эксперимента я увеличил начальное значение до 16 миллионов целых чисел, в данном случае сортировка дала результат в чуть более 4 секунд. Без использования insertion sort, сортировка занимает около 4, 5 секунд, а с ней и установленным threshold в размере 60 сортировка занимает чуть менее 4 секунд, что составляет около 10% увеличении производительности.
В данном эксперименте гибридная сортировка показала, что используя квадратичные алгоритмы для сортировки подмассивов увеличивает производительность алгоритма. И чем больше массив по размеру, тем заметней увеличение производительности.
static final int threshold = 60; // Insertion sort при <= threshold
public static void main(String[] args) {
int[] unsortedArr = new int[16 * 1024 * 1024];
Random random = new Random();
for (int i = 0; i < unsortedArr.length; i++)
unsortedArr[i] = random.nextInt();
long start = System.currentTimeMillis();
mergeSort(unsortedArr, 0, unsortedArr.length);
long end = System.currentTimeMillis();
System.out.println("Время (мс): " + (end - start));
}
static void swap(int[] arr, int first, int last) {
int tmp = arr[first];
arr[first] = arr[last];
arr[last] = tmp;
}
static void merge(int[] arr, int a, int b, int c, int d, int e) {
while (a < b && c < d)
swap(arr, e++, arr[b] < arr[c] ? a++ : c++);
while (a < b)
swap(arr, e++, a++);
while (c < d)
swap(arr, e++, c++);
}
static void mainSort(int[] a, int b, int e, int w) {
int m;
if (e - b > 1) {
m = b + (e - b) / 2;
mergeSort(a, b, m);
mergeSort(a, m, e);
merge(a, b, m, m, e, w);
} else {
while (b < e) {
swap(a, b++, w++);
}
}
}
static void mergeSort(int[] a, int b, int e) {
int m, n, w, x;
int t;
// Используем Insertion sort если <= threshold
if (e - b <= threshold) {
for(n = b+1; n < e; n++) {
t = a[n];
m = n-1;
while(m >= b && a[m] > t) {
a[m+1] = a[m];
m--;
}
a[m+1] = t;
}
return;
}
if (e - b > 1) {
m = b + (e - b) / 2;
w = b + e - m;
wsort(a, b, m, w);
while (w - b > 2) {
// w = опорная точка (середина)
n = w;
w = b + (n - b + 1) / 2;
x = b + n - w;
wsort(a, w, n, b);
merge(a, b, x, n, e, w);
}
for (n = w; n > b; --n) {
t = a[n-1];
for (m = n; m < e && a[m] < t; ++m)
a[m-1] = a[m];
a[m-1] = t;
}
}
}
FairyFox5700
IlliaKov
galaxyair
BogdanDudnik
Adaptive due to sub-algorithms Адаптивність за рахунок під-алгоритмів
Implement a recursive O(n log n) sorting algorithm (e.g. quicksort or merge sort), and for small sub-array sizes use one of the O(n^2) algorithms (insertion, selection, bubble, ...) Check if this will speedup the overall algorithm, and by how much Experimentally select the optimal threshold values for the transition to a quadratic algorithm Consider adaptive and nonadaptive implementations of a quadratic algorithm and compare their work on those arrays where adaptive algorithms are more efficient. Determine the effect of the adaptivity of the quadratic sub-algorithm on the duration of the algorithm as a whole This task is more complex, but it is worth more points. Can be done in teams. You can implement various combinations of algorithms, in different programming languages, ...
Реалізувати рекурсивний алгоритм сортування quicksort або merge sort, причому для маленьких розмірів під-масивів використовувати один з квадратичних алгоритмів (insertion, selection, bubble, …) Перевірити, чи буде від цього прискорення загального алгоритму, і на скільки Підібрати експериментально оптимальні значення порогу для переходу до квадратичного алгоритму Розглянути адаптивні та неадаптивні реалізації квадратичного алгоритму і порівняти їх роботу для тих масивів, де адаптивність дає перевагу. Визначити, який вплив має адаптивність квадратичного під-алгоритму на час роботи алгоритму в цілому Це завдання є більш складним, але за нього буде більше балів. Можна виконувати в командах. Можна реалізовувати різні комбінації алгоритмів, на різних мовах програмування, …