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

Действие алгоритма на примере сортировки случайных точек.

Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (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)