Сортировка чёт-нечет
Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.
Описание алгоритма
Заводится флаг, определяющий отсортирован ли массив. В начале итерации ставится в состояние «истина», далее каждый нечётный элемент сверяется с последующим и если они стоят в неправильном порядке (предыдущий больше следующего), то они меняются местами, и флаг ставится в состояние «ложь». То же самое делается с чётными элементами. Алгоритм не прекращает работу, пока флаг не останется в состоянии «истина».
Реализация на С++
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 'Массив успешно отсортирован';
// }
}
Литература
- Кнут Д. Искусство программирования. Том 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)