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

Odd-even sort

Дія алгоритму на прикладі випадкових даних
Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	$O(n^{2})$
Просторова складність у найгіршому випадку	$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