Odd-even transposition sort dirancang untuk model array prosesor dengan elemen-elemen
processing yang disusun menjadi mesh satu dimensi.
Anggap A = (a0, a1, ..., an-1) adalah himpunan n elemen yang akan di-sort. Setiap n elemen
processing berisi dua variabel lokal: a, elemen unik dari array A, dan t, variabel yang berisi
nilai yang diambil dari elemen processing tetangganya.
Algoritma melakukan n/2 iterasi, dan setiap iterasi memiliki dua fase:
1. odd-even exchange: nilai a pada setiap prosesor bernomer ganjil (kecuali prosesor n-1)
dibandingkan dengan nilai a yang tersimpan di prosesor berikutnya. Nlai-nilai ditukar,
jika perlu, sehingga prosesor dengan nomer lebih kecil berisi nilai yang lebih kecil.
2. even-odd exchange: nilai a pada setiap prosesor bernomer genap dibandingkan dengan
nilai a yang tersimpan di prosesor berikutnya. Nlai-nilai ditukar, jika perlu, sehingga
prosesor dengan nomer lebih kecil berisi nilai yang lebih kecil.
Setelah n/2 iterasi, nilai-nilai harus ter-sort.
ODD-EVEN TRANSPOSITION SORT (ONE-DIMENSIONAL MESH PROCESSOR
ARRAY):
Parameter n
Global i
Local a {element to be sorted}
t {element taken from adjacent processor}
begin
for i ← 1 to n/2 do
for all Pj, where 0 ≤ j ≤ n-1 do
if j < n-1 and odd(j) then {Odd-even exchange}
t ⇐ successor(a) {Get value from successor}
successor(a)⇐max(a,t) {Give away larger val}
a ← min(a,t) {Keep smaller value}
endif
if even(j) then {Even-odd exchange}
t ⇐ successor(a) {Get value from successor}
successor(a)⇐max(a,t) {Give away larger val}
a ← min(a,t) {Keep smaller value}
endif
endfor
endfor
end
Odd-even transposition sort dari delapan nilai pada model array prosesor mesh satu dimensi:
Indeks: 0 1 2 3 4 5 6 7
Nilai awal: G H F D E C B A
Setelah odd-even exchange: G F
Setelah even-odd exchange: F
Setelah odd-even exchange: F D
Setelah even-odd exchange: D
Setelah odd-even exchange: D B
Setelah even-odd exchange: B
Setelah odd-even exchange: B A
Setelah even-odd exchange: A
Teorema:
Kompleksitas sorting n elemen pada array prosesor mesh satu dimensi dengan n prosesor
menggunakan odd-even transposition sort adalah Θ(n).
Bukti:
Bukti berdasar fakta bahwa setelah i iterasi loop for luar, tidak ada elemen yang bisa lebih
jauh dari n -2i posisi dari posisi akhir dan ter-sortnya. Dengan demikian, n/2 iterasi cukup
untuk men-sort elemen-elemen tsb, dan kompleksitas waktu algoritma paralel adalah Θ(n),
jika diberikan n elemen processing.
