Ответы Mail.ru
Программирование
Android
C/C++
C#
iOS
Java
JavaScript
jQuery
SQL
Perl
PHP
Python
Веб-дизайн
Верстка, CSS, HTML, SVG
Системное администрирование
Другие языки и технологии
Лидеры категории
Лена-пена
М.И.
Y.Nine
•••
Искусственный Интеллект
Искусственный Интеллект
Искусственный Интеллект
Сравнение скорости сортировки выбором и сортировки слиянием (SelectionSort vs MergeSort)
Святослав Балема
(241),
закрыт
1 год назад
Провёл очень много тестов и на практике всё очень отличается от теории. Сортировка выбором быстрее для сортировки массива из элементов 16 +-, но с большими массивами очень медленная, сортировка слиянием в этом случае будет быстрее. НО, есть один нюанс, при сортировке от, примерно, 800 000 элементов сортировка слиянием становится медленнее чем сортировка выбором. Кто-то может объяснить почему? Я весь день пытаюсь разобраться но в теории всё должно быть наоборот.
Дополнен 1 год назад
Вот график: синее - слиянием, красное - выбором.
Я вообще молчу о том, что время сортировки выбором должно возрастать по О (n^2), а у меня время возрастает как-то линейно (я проверял 2 разные реализации сортировки выбором и обе дали одинаковые результаты)
Я вообще молчу о том, что время сортировки выбором должно возрастать по О (n^2), а у меня время возрастает как-то линейно (я проверял 2 разные реализации сортировки выбором и обе дали одинаковые результаты)
Лучший ответ
Def
(37036)
1 год назад
Обычно при таких тестах возникают проблемы в трех местах - 1. Ошибка в алгоритме ( используйте не свой, а библиотечный код для контроля), 2. некорректая методика замеров (например, замеряется не выполнение алгоритма, а время на некорректную передачу данных (генерацию или считывание тестовых данных, копирование вместо передачи по адресу, и т.п.)), 3. воздействие со стороны среды выполнения/программной реализации (сборка мусора в яве, своп в виртуальную память в плюсах...) - для снижения такого воздействия тест проверяют не на высокоуровневых языках, а, например, на ассемблере как у Кнута.
Остальные ответы
*Симфония* {Сердца}
(6342)
1 год назад
Вагоны всегда ходят по рельсам. Пишите правильно.
Святослав БалемаУченик (241)
1 год назад
я всё правильно написал. Сортировка выбором должна быть медленнее с возрастанием размера массива, а сортировка слиянием должна быть быстрее, но у меня наоборот
Андрей
(425994)
1 год назад
Главная твой проблема - использование логарифмических шкал по обеим осям. Ты просто не умеешь работать с таким графиком.
Если ты нарисуешь график своих результатов сортирови выбором на линейной шкале, то получишь параболу: при увеличении объёма данных в 2 раза время у тебя растёт в 4 раза.
Любой полином будет выглядеть на логарифмическом графике прямой линией.
Что касается сортировки слиянием, то какие именно данные ты сортируешь? Если у тебя 800000 элементов имеют всего 100 уникальных значений и если у тебя каждое значение уникально (800000 неповторяющихся значений) - результаты сортировок будут заметно разными. А сортировка строк (медленная операция сравнения) даст совсем не те результаты, что сортировка чисел (очень быстрая операция сравнения).
Опубликуй код сортировок. Полагаю, ты что-то напахал. Возможно, ты в процессе сортировки слиянием многократно выделяешь / освобождаешь память - что очень медленно.
Что с процессорным кэшем во время сортировки? Если ты сортируешь, например, байты, то в сортировке выбором весь массив может влезть в кэш современного процессора, тогда как при сортировке слиянием происходит переброс данных между далеко расположенными участками памяти.
Если ты нарисуешь график своих результатов сортирови выбором на линейной шкале, то получишь параболу: при увеличении объёма данных в 2 раза время у тебя растёт в 4 раза.
Любой полином будет выглядеть на логарифмическом графике прямой линией.
Что касается сортировки слиянием, то какие именно данные ты сортируешь? Если у тебя 800000 элементов имеют всего 100 уникальных значений и если у тебя каждое значение уникально (800000 неповторяющихся значений) - результаты сортировок будут заметно разными. А сортировка строк (медленная операция сравнения) даст совсем не те результаты, что сортировка чисел (очень быстрая операция сравнения).
Опубликуй код сортировок. Полагаю, ты что-то напахал. Возможно, ты в процессе сортировки слиянием многократно выделяешь / освобождаешь память - что очень медленно.
Что с процессорным кэшем во время сортировки? Если ты сортируешь, например, байты, то в сортировке выбором весь массив может влезть в кэш современного процессора, тогда как при сортировке слиянием происходит переброс данных между далеко расположенными участками памяти.
Святослав БалемаУченик (241)
1 год назад
int merge(int arr[], int beg, int mid, int end) {
int i = beg,
j = mid + 1,
index = beg,
k,
* temp,
size;
size = end + 1;
temp = (int*)malloc(sizeof(int) * size);
if (!temp) return 1;
while ((i <= mid) && (j <= end)) {
if (arr[i] < arr[j]) {
temp[index] = arr[i];
i++;
}
else {
temp[index] = arr[j];
j++;
}
index++;
}
if (i > mid) {
while (j <= end) {
temp[index] = arr[j];
j++;
index++;
}
}
else {
while (i <= mid) {
temp[index] = arr[i];
i++;
index++;
}
}
for (k = beg; k < index; k++)
arr[k] = temp[k];
free(temp);
return 0;
}
int i = beg,
j = mid + 1,
index = beg,
k,
* temp,
size;
size = end + 1;
temp = (int*)malloc(sizeof(int) * size);
if (!temp) return 1;
while ((i <= mid) && (j <= end)) {
if (arr[i] < arr[j]) {
temp[index] = arr[i];
i++;
}
else {
temp[index] = arr[j];
j++;
}
index++;
}
if (i > mid) {
while (j <= end) {
temp[index] = arr[j];
j++;
index++;
}
}
else {
while (i <= mid) {
temp[index] = arr[i];
i++;
index++;
}
}
for (k = beg; k < index; k++)
arr[k] = temp[k];
free(temp);
return 0;
}
Святослав БалемаУченик (241)
1 год назад
int SortMerge(int* arr, int beg, int end) {
int mid;
if (beg < end) {
mid = (beg + end) / 2;
SortMerge(arr, beg, mid);
SortMerge(arr, mid + 1, end);
if (!merge(arr, beg, mid, end))
return 0;
else
return 1;
}
}
int mid;
if (beg < end) {
mid = (beg + end) / 2;
SortMerge(arr, beg, mid);
SortMerge(arr, mid + 1, end);
if (!merge(arr, beg, mid, end))
return 0;
else
return 1;
}
}
Андрей
Высший разум
(425994)
Неэффективная рекурсивная реализация, в каждом вызове merge делаешь malloc/free, сначала копируешь в temp, а потом обратно в arr... Очень большие накладные расходы.
Нужен один создаваемый перед началом сортировки массив temp - того же размера, что и arr.
На самом глубоком уровне рекурсии сливаем участки из arr в temp. На предпоследнем - из temp в arr, на втором с конца - из arr в temp и т.д.
Если общая глубина рекурсии чётная - отсортированный массив сразу получаем в arr. А если нечётная - на самом глубоком уровне просто переставляем 2 соседних элемента arr в нужном порядке и переходим к варианту с чётной глубиной.
Но часто выгоднее останавливать слияние, когда в блоке останется несколько элементов (например, <= 10) и сортировать такой блок не слиянием, а, например, пузырьком.
Похожие вопросы