奇偶排序

奇偶排序(英語:Odd–even sort),或奇偶換位排序磚排序[1],是一種相對簡單的排序演算法,最初發明用於有本地互連的平行計算。這是與泡沫排序特點類似的一種比較排序

奇偶排序
使用奇偶排序法對一列亂數字進行排序的過程
概況
類別排序演算法
資料結構陣列
複雜度
最壞時間複雜度
最佳時間複雜度
最佳解
相關變數的定義

該演算法中,通過比較陣列中相鄰的(奇-偶)位置數字對,如果該奇偶對是錯誤的順序(第一個大於第二個),則交換。下一步重複該操作,但針對所有的(偶-奇)位置數字對。如此交替進行下去。

處理器陣列的排序

平行計算排序中,每個處理器對應處理一個值,並僅有與左右鄰居的本地互連。所有處理器可同時與鄰居進行比較、交換操作,交替以奇-偶、偶-奇的順序。該演算法由Habermann在1972年最初發表並展現了在並列處理上的效率。[2]

該演算法可以有效地延伸到每個處理器擁有多個值的情況。在Baudet–Stevenson奇偶合併分割演算法中,每個處理器在每一步對自己所擁有的子陣列進行排序,然後與鄰居執行合併分割或換位合併。[3]

Batcher奇偶合併排序

Batcher奇偶合併排序是一種相關但更有效率的排序演算法,採用比較-交換和完美-洗牌操作。[4]

Batcher的方法在擁有廣泛互連的平行計算處理器上效率不錯。[5]

程式碼

C語言

void odd_even_sort(int arr[], int len) {
	int odd_even, i;
	int temp;
	int sorted = 0;
	while (!sorted) {
		sorted = 1;
		for (odd_even = 0; odd_even < 2; odd_even++)
			for (i = odd_even; i < len - 1; i += 2)
				if (arr[i] > arr[i + 1]) {
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					sorted = 0;
				}
	}
}

C++

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void odd_even_sort(T arr[], int len) {
	int odd_even, i;
	bool sorted = false;
	while (!sorted) {
		sorted = true;
		for (odd_even = 0; odd_even < 2; odd_even++)
			for (i = odd_even; i < len - 1; i += 2)
				if (arr[i] > arr[i + 1]) {
					swap(arr[i], arr[i + 1]);
					sorted = false;
				}
	}
}

Python

# 假设已有列表a等待排序
while True:
    sorted = True
    # 处理奇-偶对
    for i in xrange(1, len(a)-1, 2):
        if a[i] > a[i+1]:
           a[i], a[i+1] = a[i+1], a[i] # 交换
           sorted = False
    # 处理偶-奇对
    for i in xrange(0, len(a)-1, 2):
        if a[i] > a[i+1]:
           a[i], a[i+1] = a[i+1], a[i] # 交换
           sorted = False
    if sorted:
        break

JavaScript

Array.prototype.odd_even_sort = function() {
	var odd_even, i;
	var temp;
	var sorted = 0;
	while (!sorted) {
		sorted = 1;
		for ( odd_even = 0; odd_even < 2; odd_even++)
			for ( i = odd_even; i < this.length - 1; i += 2)
				if (this[i] > this[i + 1]) {
					temp = this[i];
					this[i] = this[i + 1];
					this[i + 1] = temp;
					sorted = 0;
				}
	}
	return this;
};

PHP

function swap(&$x, &$y) {
	$t = $x;
	$x = $y;
	$y = $t;
}
function odd_even_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
	$sorted = 0;
	while (!$sorted) {
		$sorted = 1;
		for ($odd_even = 0; $odd_even < 2; $odd_even++)
			for ($i = $odd_even; $i < count($arr) - 1; $i += 2)
				if ($arr[$i] > $arr[$i + 1]) {
					swap($arr[$i], $arr[$i + 1]);
					$sorted = 0;
				}
	}
}

參考文獻

  1. ^ Phillips, Malcolm. Array Sorting. [3 August 2011]. (Sort Techniques 原始內容 請檢查|url=值 (幫助)存檔於2011年10月28日). 
  2. ^ N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151).
  3. ^ S. Lakshmivarahan, S. K. Dhall, and L. L. Miller, Franz L. Alt and Marshall C. Yovits , 編, Parallel Sorting Algorithms, Advances in computers (Academic Press), 1984, 23: 295–351, ISBN 9780120121236 
  4. ^ Robert Sedgewick. Algorithms in Java, Parts 1-4 3rd. Addison-Wesley Professional. 2003: 454–464. ISBN 9780201361209. 
  5. ^ Allen Kent and James G. Williams. Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. 1993: 33–38. ISBN 9780824722821. 

外部連結