C/C++

Сравнение скорости сортировки выбором и сортировки слиянием (SelectionSort vs MergeSort)

Провёл очень много тестов и на практике всё очень отличается от теории. Сортировка выбором быстрее для сортировки массива из элементов 16 +-, но с большими массивами очень медленная, сортировка слиянием в этом случае будет быстрее. НО, есть один нюанс, при сортировке от, примерно, 800 000 элементов сортировка слиянием становится медленнее чем сортировка выбором. Кто-то может объяснить почему? Я весь день пытаюсь разобраться но в теории всё должно быть наоборот.
Игорь Старченко
Игорь Старченко
241
Обычно при таких тестах возникают проблемы в трех местах - 1. Ошибка в алгоритме ( используйте не свой, а библиотечный код для контроля), 2. некорректая методика замеров (например, замеряется не выполнение алгоритма, а время на некорректную передачу данных (генерацию или считывание тестовых данных, копирование вместо передачи по адресу, и т.п.)), 3. воздействие со стороны среды выполнения/программной реализации (сборка мусора в яве, своп в виртуальную память в плюсах...) - для снижения такого воздействия тест проверяют не на высокоуровневых языках, а, например, на ассемблере как у Кнута.
Анатолий Олещук
Анатолий Олещук
30 155
Лучший ответ
Главная твой проблема - использование логарифмических шкал по обеим осям. Ты просто не умеешь работать с таким графиком.
Если ты нарисуешь график своих результатов сортирови выбором на линейной шкале, то получишь параболу: при увеличении объёма данных в 2 раза время у тебя растёт в 4 раза.

Любой полином будет выглядеть на логарифмическом графике прямой линией.

Что касается сортировки слиянием, то какие именно данные ты сортируешь? Если у тебя 800000 элементов имеют всего 100 уникальных значений и если у тебя каждое значение уникально (800000 неповторяющихся значений) - результаты сортировок будут заметно разными. А сортировка строк (медленная операция сравнения) даст совсем не те результаты, что сортировка чисел (очень быстрая операция сравнения).

Опубликуй код сортировок. Полагаю, ты что-то напахал. Возможно, ты в процессе сортировки слиянием многократно выделяешь / освобождаешь память - что очень медленно.

Что с процессорным кэшем во время сортировки? Если ты сортируешь, например, байты, то в сортировке выбором весь массив может влезть в кэш современного процессора, тогда как при сортировке слиянием происходит переброс данных между далеко расположенными участками памяти.
ЮМ
Юрий Маслов
83 608
Игорь Старченко 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 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;
}
}
Вагоны всегда ходят по рельсам. Пишите правильно.
Махмут Исмагилов
Махмут Исмагилов
6 334
Игорь Старченко я всё правильно написал. Сортировка выбором должна быть медленнее с возрастанием размера массива, а сортировка слиянием должна быть быстрее, но у меня наоборот

Похожие вопросы