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

Odd-even sort

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

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 

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (квітень 2017)

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.