“SORTING DALAM C++”
1.
Alat dan Bahan
Alat dan bahan yang diperlukan
adalah: Personal Computer (PC)/Laptop,
Terminal, dan Codeblocks.
2. Teori
Singkat
Algoritma pengurutan (sorting algorithm)
adalah algoritma yang mengurutkan data menggunakan aturan tertentu. Ada 2
macam, yaitu urut naik (ascending)
dan urut turun descending)
a. urut naik (ascending)
yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
b. urut turun (descending)
yaitu data yang mempunyai nilai paling besar sampai paling kecil.
Ada 2 metode sorting yang
dipelajari, yaitu Buble dan Quick
Sort.
2.1. Pengurutan Gelembung (Bubble
Sort)
Pengurutan gelembung adalah algoritma pengurutan yang paling tua
dan sederhana untuk diimplementasikan. Algoritma ini juga cukup mudah untuk
dimengerti. Algoritma pengurutan gelembung dalam implementasi bahasa C adalah
sebagai berikut.
Pengurutan gelembung ini menggunakan dua buah kalang (loop) for.
Kalang yang pertama melakukan travesal dari indeks terkecil sedangkan kalang
yang kedua melakukan traversal dari indeks terbesar. Kalang yang satu berada di
dalam kalang yang lain dan panjang masing-masing tergantung pada banyaknya
elemen. Siklus yang pertama melakukan n-1 perbandingan, siklus yang kedua
melakukan n-2 perbandingan, siklus yang ketiga melakukan n-3, dan seterusnya.
Sehingga total semua perbandingan
(n-1) + (n-2) + .. +1
yang dapat disederhanakan menjadi n(n-1)/2.
Algoritma ini bekerja dengan cara membandingkan nilai tiap elemen
dalam tabel dengan elemen setelahnya, dan menukar nilainya jika sesuai dengan
kondisi yang diperlukan. Proses ini akan terus berulang hingga seluruh elemen
dalam tabel telah diproses dan elemen dalam tabel telah terurut.
Algoritma pengurutan gelembung ini adalah algoritma yang paling
lamban dan tidak mangkus dibandingkan dengan algoritma pengurutan yang lain
dalam penggunaan secara umum. Dalam kasus terbaik (yaitu list sudah terurut),
kompleksitas algoritma pengurutan gelembung adalah O(n). Namun, untuk
kasus umum, kompleksitas algoritma pengurutan gelembung adalah O(n2 ).
Grafik di atas menggambarkan kompleksitas algoritma dari pengurutan
gelembung.
2.2. Pengurutan Cepat (Quick Sort)
Algoritma quick sort sangat sederhana dalam teori, tetapi
sangat sulit untuk diterjemahkan ke dalam sebuah code karena pengurutan
dilakukan dalam sebuah list dan diproses secara rekursif.
Algoritma ini terdisi dari empat langkah (yang mana menyerupai merge sort)
yaitu :
- Memilih sebuah elemen untuk dijadikan poros atau pivot point (biasanya elemen paling kiri dari tabel).
- Membagi tabel menjadi dua bagian, satu dengan elemen yang lebih besar dari poros, dan satu lagi untuk elemen yang lebih kecil dari poros.
- Mengulang algoritma untuk kedua buah tabel secara rekursif.
Tingkat keefektifan dari algoritma ini dangat bergantung pada
elemen yang dipilih menjadi poros. Kasus terburuk terjadi ketika tabel sudah
terurut dan elemen terkecil di sebelah kiri menjadi poros. Kasus ini mempunyai kompleksitas
algoritma O(n 2 ). Maka dari itu sangat disarankan untuk memilih poros
bukan dari elemen paling kiri dari tabel, tetapi dipilih secara random.
Selama poros dipilih secara random, algoritma quick sort
mempunyai kompleksitas algoritma sebesar O(n log n).
Algoritma quick sort mengurutkan dengan sangat cepat, namun
algoritma ini sangat komplex dan diproses secara rekursif. Sanat
memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus
khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat
dibandingkan algoritma quick sort.
Walaupun begitu algoritma quick sort tidak selalu merupakan
pilihan yang terbaik. Seperti yang telah disebutkan sebelumnya, algoritma ini
dilakukan secara rekursif yang berarti jika dilakukan untuk tabel yang
berukuran sangat besar, walaupun cepat, dapat menghabiskan memori yang besar
pula. Selain itu, algoritma ini adalah algoritma yang terlalu komplex
untuk mengurutkan tabel yang berukuran kecil (hanya puluhan elemen misalnya).
Selain itu algoritma quick sort mempunyai tingkat efisiensi yang buruk
ketika dioperasikan pada tabel yang hampir terurut atau pada tabel yang terurut
menurun.
Grafik di atas menggambarkan kompleksitas
algoritma dari quick sort.
2.3. Pengurutan Dengan Penggabungan (Merge Sort)
Algoritma
merge sort membagi (split) tabel menjadi dua tabel sama besar.
Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali
untuk membentuk tabel yang terurut.
Implementasi
dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk
menyimpan elemen dari tabel yang telah dibagi dua dan satu untuk menyimpan
elemen yang telah teurut. Namun algoritma ini dapat juga dilakukan langsung
pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Di bawah ini
adalah algoritma untuk merge sort yang dilakukan pada dua tabel.
Karena
algoritma merge sort adalah algoritma yang dijalankan secara rekursif maka T(n)
dari algoritma ini adalah
Sehingga, algoritma merge sort memiliki kompleksitas
algoritma O(n log n). Algoritma merge sort ini sebenernya lebih
cepat dibandingkan heap sort untuk tabel yang lebih besar. Namun,
algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar
karena dilakukan secara rekursif dan memakai dua tabel. Hal ini
menyebabkan algoritma ini kurang banyak dipakai.
Grafik di atas menggambarkan kompleksitas
algoritma dari merge sort.
Sumber :
Tidak ada komentar:
Posting Komentar