SortingLanjutFase E–FE1E5

BITONIC SORT

Bitonic Sort adalah algoritma pengurutan berbasis jaringan perbandingan (sorting network) dengan urutan operasi compare-swap yang tetap, tidak bergantung pada data. Ia bekerja membentuk barisan bitonik lalu menggabungkannya, dengan pasangan elemen dan arah pembandingan ditentukan melalui operasi bit (i ^ j dan i & k). Struktur tetap ini membuatnya sangat cocok untuk eksekusi paralel. Visualisasi menampilkan jaringan jalur dengan operasi tukar antar elemen hingga terurut.

Example use case

Pengurutan paralel berkinerja tinggi pada GPU atau perangkat keras (FPGA) untuk pemrosesan data masif.

Syllabus

Mengurutkan lewat jaringan compare-swap dengan urutan tetap yang tidak bergantung pada isi data, sehingga banyak perbandingan bisa jalan bersamaan.

Objectives

·Memahami apa itu sorting network dan mengapa polanya tetap
·Menjelaskan bagaimana operasi bit (i ^ j dan i & k) menentukan pasangan dan arah tukar
·Menerapkan konsep barisan bitonik untuk pengurutan paralel

How It Works

·Data dibentuk menjadi barisan bitonik: naik dulu lalu turun
·Elemen dipasangkan lewat operasi XOR indeks, arah tukar dari bit i & k
·Tiap pasangan dibandingkan dan ditukar bila urutannya salah
·Barisan digabung bertahap sampai seluruh data terurut
·Karena polanya tetap, banyak perbandingan dijalankan serentak

Prerequisites

·Bubble Sort
·Operasi bit dasar
·Konsep paralel

Real-World Uses

·Mengurutkan data grafis super cepat di GPU saat main game berat
·Pemrosesan data masif di perangkat keras khusus seperti FPGA

Complexity O(n log^2 n)