Парне-непарне сортування

Odd-even sort чи Odd-even transposition sort — в інформатиці, парне-непарне сортування (також відоме як сортування цеглинами) є відносно простим алгоритмом сортування, розробленим спочатку для використання на паралельних процесорах з локальними взаємозв'язками. Воно порівнюється з сортуванням бульбашкою, з яким поділяє багато характеристик. Алгоритм діє наступним чином: порівнюються всі парні / непарні пари проіндексованих суміжних елементів в списку, і якщо пара знаходиться в неправильному порядку (перший більше, ніж другий) елементи міняються місцями. Наступним кроком повторює це для парних / непарних індексованих пар (суміжних елементів). Чергуються парні/непарні та непарні/парні кроки, поки список не буде відсортований.

Odd-even sort

Дія алгоритму на прикладі випадкових даних
Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	${\displaystyle O(n^{2})}$
Просторова складність у найгіршому випадку	${\displaystyle O(1)}$
Оптимальний	ні

Алгоритм

Однопроцесорний алгоритм, як , є простим, але не дуже ефективним.

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;  }  }  } } 

Приклад алгоритму в :

 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