Bitonic Merge

Algoritma ini menjadi dasar untuk algoritma-algoritma sorting dengan waktu proses poli-logaritmik pada beberapa model komputasi paralel. Operasi dasarnya adalah Compare-Exchange: dua buah angka diarahkan masuk ke sebuah Comparator, di dalam comparator ini kedua nilai jika diperlukan akan dipertukarkan, sehingga akan berada pada urutan yang dikehendaki

Definisi 10.1 Bitonic Sequence adalah sederetan nilai \( a_{0}, \cdots ,a_{n-1}\) dengan sifat bahwa

1. ada sebuah index i , dimana \( 0\leq i\leq n-1\), sedemikian sehingga a₀  menaik secara monoton ke a_i  dan a_i menurun secara monoton hingga a_n-1 , atau
2. ada sebuah pergeseran index yang berputar (cyclic shift) sehingga kondisi yang pertama terpenuhi

Coba Anda perhatikan sebuah grafik barisan bitonic di bawah ini, dia akan memiliki paling banyak ‘satu puncak’ dan ‘satu lembah’. Jangan lupa bahwa barisan ini ‘memutar’ dari elemen yang terakhir kembali ke elemen yang pertama.

Sebuah langkah compare-exchange bisa memecah sebuah barisan bitonic tunggal menjadi 2 (dua) buah barisan bitonic, sebagaimana disebutkan dalam Lemma 10.1 berikut ini :

Lemma 10.1 Jika n adalah genap, maka n/2 buah comparator cukup untuk mentransformasikan sebuah barisan bitonic dengan n buah nilai, \( a_0, a_1, a_2, \cdots , a_{n-2},a_{n-1}\) menjadi 2 (dua) buah barisan bitonic dengan n/2 buah nilai,

\( min(a_0,a_{n/2}), min(a_1,a_{n/2+1}),\cdots ,min(a_{n/2-1},a_{n-1})\)
dan
\( max(a_0,a_{n/2}), max(a_1,a_{n/2+1}),\cdots ,max(a_{n/2-1},a_{n-1})\)

Sedemikian sehingga tidak ada nilai yang terletak pada barisan yang pertama adalah lebih besar dari nilai yang terletak pada barisan yang kedua.

Anggaplah kita memiliki sebuah barisan bitonic, sebuah langkah  compare-exchange membagi barisan ini menjadi dua buah barisan bitonic yang sama panjang yaitu n/2 . Dengan melakukan langkah ini secara rekursif akan menghasilkan barisan yang terurut.

 

Atau dengan kata lain, jika diberikan sebuah barisan bitonic dengan panjang n = 2^k , dimana k > 0, maka k buah langkah compare-exchange cukup untuk menghasilkan barisan yang terurut

Berikut ini adalah contoh mengurutkan barisan dengan panjang 16 yang di jalankan dalam 4 (empat) langkah compare-exchange.

10-12