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

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

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

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

Реализация на C++[править | править код]

template < typename T, size_t N > void oddEvenSorting(T (&array)[N]) { 	for (size_t i = 0; i < N; i++) { 	    // (i % 2) ? 0 : 1 возвращает 1, если i четное, 0, если i не четное 		for (size_t j = (i % 2) ? 0 : 1; j + 1 < N; j += 2) { 			if (array[j] > array[j + 1]) { 				std::swap(array[j], array[j + 1]); 			} 		} 	} } 

Реализация на JavaScript[править | править код]

function oddEvenSorting(array) {     const arrayLength = array.length; //длина массива 	for (let i = 0; i < arrayLength; i++) { 	    // (i % 2) ? 0 : 1 возвращает 0, если i четное, 1, если i не четное 		for (let j = (i % 2) ? 0 : 1; j < arrayLength - 1; j += 2) { 			if (array[j] > array[j + 1]) 				[array[j], array[j + 1]] = [array[j + 1], array[j]]; //swap 		}     }     return array; } 

Реализация на PHP[править | править код]

function FunctionOddEvenSort(&$array) { 	$lengthArray = count($array); 	$sorted = false; 	while (!$sorted) { 		$sorted = true; 		for ($i = 0; $i < $lengthArray - 1; $i += 2) { 			if ($array[$i] > $array[$i + 1]) { 				FunctionSwapVariables($array[$i], $array[$i + 1]); 				$sorted = false; 			} 		} 		for ($i = 1; $i < $lengthArray - 2; $i += 2) { 			if ($array[$i] > $array[$i + 1]) { 				FunctionSwapVariables($array[$i], $array[$i + 1]); 				$sorted = false; 			} 		} 	}  	// for ($x = 0; $x < $lengthArray; $x++) {  	// 	if (!$sorted) { 	// 		$sorted = true; 	// 		for ($i = 0; $i < $lengthArray - 1; $i += 2) { 	// 			if ($array[$i] > $array[$i + 1]) { 	// 				FunctionSwapVariables($array[$i], $array[$i + 1]); 	// 				$sorted = false; 	// 			} 	// 		} 	// 		for ($i = 1; $i < $lengthArray - 2; $i += 2) { 	// 			if ($array[$i] > $array[$i + 1]) { 	// 				FunctionSwapVariables($array[$i], $array[$i + 1]); 	// 				$sorted = false; 	// 			} 	// 		} 	// 	} else return 'Массив успешно отсортирован'; 	// } } 

Реализация на Swift[править | править код]

func sortArray(array: inout [Int]) {     var sorted = false          while !sorted {         sorted = true         for k in stride(from: 0, to: array.count - 1, by: 2){             if array[k] > array[k + 1] {                 array.swapAt(k, k+1)                 sorted = false             }         }                  for k in stride(from: 1, to: array.count - 1, by: 2){             if array[k] > array[k + 1] {                 array.swapAt(k, k+1)                 sorted = false             }         }     } } 

Литература[править | править код]

• Кнут Д. Искусство программирования. Том 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)

Для улучшения этой статьи желательно: Проставить сноски, внести более точные указания на источники. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.