Odd-even sort
Odd-even sort чи Odd-even transposition sort — в інформатиці, парне-непарне сортування (також відоме як сортування цеглинами) є відносно простим алгоритмом сортування, розробленим спочатку для використання на паралельних процесорах з локальними взаємозв'язками. Воно порівнюється з сортуванням бульбашкою, з яким поділяє багато характеристик. Алгоритм діє наступним чином: порівнюються всі парні / непарні пари проіндексованих суміжних елементів в списку, і якщо пара знаходиться в неправильному порядку (перший більше, ніж другий) елементи міняються місцями. Наступним кроком повторює це для парних / непарних індексованих пар (суміжних елементів). Чергуються парні/непарні та непарні/парні кроки, поки список не буде відсортований.
 Дія алгоритму на прикладі випадкових даних | |
| Клас | Алгоритм сортування |
|---|---|
| Структура даних | Масив |
| Найгірша швидкодія | |
| Просторова складність у найгіршому випадку | |
| Оптимальний | ні |
Алгоритм
Однопроцесорний алгоритм, як BubbleSort, є простим але не дуже ефективним.
function oddEvenSort(list) {
function swap( list, i, j ){
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
var sorted = false;
while(!sorted)
{
sorted = true;
for(var i = 1; i < list.length-1; i += 2)
{
if(list[i] > list[i+1])
{
swap(list, i, i+1);
sorted = false;
}
}
for(var i = 0; i < list.length-1; i += 2)
{
if(list[i] > list[i+1])
{
swap(list, i, i+1);
sorted = false;
}
}
}
}
Приклад алгоритму в C++:
template <class T>
void OddEvenSort (T a[], int n)
{
for (int i = 0 ; i < n ; i++)
{
if (i & 1) // 'i' is odd
{
for (int j = 2 ; j < n ; j += 2)
{
if (a[j] < a[j-1])
swap (a[j-1], a[j]) ;
}
}
else
{
for (int j = 1 ; j < n ; j += 2)
{
if (a[j] < a[j-1])
swap (a[j-1], a[j]) ;
}
}
}
}
Приклад алгоритму в php:
function oddEvenSorting(&$a) {
$n = count($a);
$sorted = false;
while (!$sorted) {
$sorted = true;
for ($i = 1; $i < ($n - 1); $i += 2) {
if ($a[$i] > $a[$i + 1]) {
list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
if ($sorted) $sorted = false;
}
}
for ($i = 0; $i < ($n - 1); $i += 2) {
if ($a[$i] > $a[$i + 1]) {
list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
if ($sorted) $sorted = false;
}
}
}
}
Приклад алгоритму в Python:
def oddevenSort(x):
sorted = False
while sorted == False:
sorted = True
for i in range(0, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
for i in range(1, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
return x
Приклад алгоритму в MATLAB/Octave:
function x = oddevenSort(x)
sorted = false;
n = length(x);
while ~sorted
sorted = true;
for ii=1:2:n-1
if x(ii) > x(ii+1)
[x(ii), x(ii+1)] = deal(x(ii+1), x(ii));
sorted = false;
end
end
for ii=2:2:n-1
if x(ii) > x(ii+1)
[x(ii), x(ii+1)] = deal(x(ii+1), x(ii));
sorted = false;
end
end
end