Алгоритм сортировки-слияния

Сортировка слиянием представляет собой алгоритм сортировки который состоит из объединения двух списков, отсортированных в один. Его принцип основан на методе deviser pour régner. Преимущество sort-to-merge заключается в том, что два списка объединяются одновременно, поэтому мы можем сделать реализацию с помощью threads.

Алгоритм известен своей эффективностью в сложности (время и память) и сортировкой списков:

Мы разрезаем данные на две равные части.
Мы сортируем данные каждого part (мы разделяем каждую часть, алгоритм становится рекурсивным).
Мы объединяем две части.

Мы рекурсивно разделяем начальный массив на два подмассива, пока массив не будет содержать только один элемент. После того, как элементы отсортированы независимо друг от друга, с этого момента backtracking и мы собираемся объединить подтаблицы до тех пор, пока не получите отсортированную стартовую доску. Слияние состоит из последовательных сравнений.

Пример

Предположим, мы хотим отсортировать следующую таблицу: [ 38, 27 ,43, 3, 9, 82, 10]

Algorithm

TriFusion ALGORITHM(T, слева, справа);

Т: таблица значений;

left,right: целое число;

center: целое число;

НАВЕРХ

IF (слева < справа) THEN

← по центру (слева + справа) / 2;

TriFusion (Т, слева, в центре);

TriFusion (Т, центр + 1, справа);

MERGE(T, влево, по центру, вправо);

FSI

FIN.

Алгоритм сортировки-слияния

Пример

Algorithm

Commentaires (0)

Laisser un commentaire

Connectez-vous pour commenter