Bitonic Merge pada Shuffle-Exchange Nework

Teorema 10.6. Sebuah daftar dengan n = 2 buah elemen yang tidak terurut dan dapat diurutkan dalam waktu \inline \Theta (log^{2}n) dengan jaringan \inline 2^{k-1}[k(k-1)+1] komparator menggunakan skema interkoneksi  shuffle-exchange secara exclusive (Stone, 1971)

openstat_bitonic_merge_10-14

Stone menyadari bahwa Pengurut Bitonic milik Batcher ini selalu membandingkan elemen-elemen dengan index yang berbeda tepat 1 bit pada bentuk biner nya. Dengan perfect shuffle, akan memperjalankan elemen pada posisi ke posisi yang ditemukan., dengan memutar tampilan biner dari satu bit ke kiri. Dengan demikian dua buah index yang tampilan biner nya berbeda tepat 1 bit dapat diperjalankan ke komparator yang sama dengan cara melakukan sejumlah shuffle tertentu.

Gambar berikut ini menunjukkan bagaimana bitonic merge dapat diimplementasi dengan menggunakan skema interkoneksi shuffle-exchange secara ekslusif.

Gambar 10-13

Gambar 10-13

 

Sangat berbeda dengan Gambar 10-10, dimana interkoneksi antar komparator nya bervariasi dari tahap ke tahap lainnya. Keseluruhan proses pengurutan dapat diselesaikan dengan menggunakan interkoneksi shuffle-exchange. Kedua algoritma membutuhkan bitonic merge untuk mengurutkan 2k elemen, tetapi ketika merge ke-di algoritma Batcher membutuhkan langkah untuk total k(k+1)/2, 

 

openstat_bitonic_merge_10-14

Algoritma

openstat_bitonic_merge_10-16 ’

 

openstat_bitonic_merge_10-17

Leave a Reply

Your email address will not be published.

Captcha Captcha Reload