Алгоритм рекурсивной сортировки (сортировка фон-Неймана).

Сортировка – это алгоритмический процесс перестановки объектов данного множества в определённом заданном порядке.

Цель сортировки – это облегчение последующего поиска элементов в отсортированном множестве.

Возможны следующие виды сортировки:
- по возрастанию элементов (каждый следующий больше предыдущего);
- по убыванию элементов (каждый следующий меньше предыдущего);
- не убыванию элементов (каждый следующий больше или равен предыдущему);
- не возрастанию элементов (каждый следующий меньше или равен предыдущему).

Алгоритм (рекурсивный)

1. Делим массив на две половины.
2. Сортируем каждую из половин отдельно.
3. Соединяем два упорядоченных массива половинного размера в один.

Рекурсивное разбиение задачи на меньшие подзадачи происходит до тех пор, пока размер массива не дойдет до единицы: любой массив длины 1 можно считать упорядоченным.

Процесс сортировки слиянием показан на рисунке

Сортировка (Left, Right)

{ Если (Left<Right)

То

{ M=[(Left+Right)/2];

Сортировка (Left, M);

Сортировка (M+1, Right);

Слияние (Left, M, M+1,Right);

}

}

Дата добавления: 2015-10-02