|
Сортировка чёт-нечет Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (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]);
}
}
}
}
Реализация на JavaScriptfunction 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;
}
Реализация на PHPfunction 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 'Массив успешно отсортирован';
// }
}
Реализация на Swiftfunc 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
}
}
}
}
Литература
|
||||||||||||||||||||||
