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

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

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

Реализация на C++(без параллельных потоков)[править | править вики-текст]

// Сортировка по возрастанию массива A размерности N
 template<class T> void OddEvenSort(T *A, int N) {
     bool Sorted = false;
     while(!Sorted) {
         Sorted = true;
         for(int i = 1; i < N - 1; i += 2) {
             if(A[i] > A[i+1]) {
                 swap(A[i], A[i+1]);
                 Sorted = false;
             }
         }
         for(int i = 0; i < N - 1; i += 2) {
             if(A[i] > A[i+1]) {
                 swap(A[i], A[i+1]);
                 Sorted = false;
             }
         }
     }
 }

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

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

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

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