Меню
Главная
Случайная статья
Настройки
|
Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.
Описание алгоритма
Заводится флаг, определяющий отсортирован ли массив. В начале итерации ставится в состояние «истина», далее каждый нечётный элемент сверяется с последующим и если они стоят в неправильном порядке (предыдущий больше следующего), то они меняются местами, и флаг ставится в состояние «ложь». То же самое делается с чётными элементами. Алгоритм не прекращает работу, пока флаг не останется в состоянии «истина».
Литература- Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — Москва: Вильямс, 2000. — ISBN 978-5-8459-0082-1.
- N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle), " CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151)
|
|