Сортировка чёт-нечет

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Действие алгоритма на примере сортировки случайных точек.

Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.

Описание алгоритма[править | править вики-текст]

Заводится флаг, определяющий отсортирован ли массив. В начале итерации ставится в состояние «истина», далее каждый нечётный элемент сверяется с последующим и если они стоят в не правильном порядке (предыдущий больше следующего), то они меняются местами, и флаг ставится в состояние «ложь». То же самое делается с чётными элементами. Алгоритм не прекращает работу, пока флаг не останется в состоянии «истина».

Реализация на С++[править | править вики-текст]

template < typename T >
void oddEvenSorting(T *array, int arrayLength){
	for (int i = 0; i < arrayLength; i++){
		for (int j = (i % 2) ? 0 : 1; j < arrayLength - 1; j += 2){
			if (array[j] > array[j + 1]){
				std::swap(array[j], array[j + 1]);
			}
		}
	}
}

Литература[править | править вики-текст]

  • Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — Москва: Вильямс, 2000. — ISBN 978-5-8459-0082-1.