ALGORITMA SORTING

Sorting adalah sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam himpunan yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang berbeda:

1. pengurutan: merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur.
2. kategorisasi: pengelompokan dan pemberian label kepada benda dengan sifat yang serupa.

Ada dua bentuk sorting yaitu secara ascending dan descending. Sorting secara ascending adalah cara mengurutkan data mulai data bernilai terkecil sampai terbesar. Sedangkan descending mengurutkan data mulai dari data terbesar sampai terkecil. Sebagai contoh misalkan diberikan data berupa bilangan berikut ini:

3 9 1 4 0 2

Hasil sorting ascending adalah 0 1 2 3 4 9, sedangkan hasil secara descending adalah 9 4 3 2 1 0.

Algoritma sorting terdiri dari beberapa algoritma seperti Bubble sort, Quick sort, Selection sort, Insertion sort, dan Merge sort yang di mana setiap jenis sorting ini memilki perbedaan satu sama lainnya. Berikut ini merupakan pembahasan umum mengenai jenis-jenis algoritma sorting yang telah dijelaskan di atas.

a.      Bubble Sort

1.      Sejarah

Mr. Bubble adalah seorang siswa Pineapple High School Convent. Selama melakukan doa harian, semua siswa dari kelas yang sama berdiri dalam satu baris dan disyaratkan bahwa setiap siswa harus berdiri berdasarkan urutan tinggi badan. Ketika siswa  tersebut berbaris untuk pertama kalinya, terjadi kekacauan. Semua siswa berteriak. "Hei kamu lebih pendek dari saya, kamu harus berdiri di depanku", "hei, berdiri di belakang", dll. Guru menyuruh mereka diam dan dia memikirkan cara untuk mengatur mereka semua.

Proses pengurutan pertama yang harus dia lakukan adalah menemukan siswa terpendek dan menempatkannya di tempat pertama, kemudian menemukan siswa yang terpendek berikutnya dan menempatkannya di tempat kedua dan seterusnya. Dia menyadari bahwa proses untuk menemukan siswa terpendek di antara sekumpulan siswa sangat rumit. Ketika ia mengamati dari atas ke bawah, terkadang dia tidak akan bisa memutuskan apakah seorang siswa yang  mendekati baris akhir lebih pendek dari siswa yang dilihatnya di baris pertama. Dia hanya bisa memutuskan siapa yang lebih pendek jika mereka berdiri di samping satu sama lain. Jadi dia menuju ke barisan awal dan mulai menukar tempat dua siswa yang berdekatan. Dia kemudian memutuskan untuk melakukan hal yang sama ke setiap siswa yang  tersisa. Dia terus melakukan hal yang sama dan akhirnya barisan siswa-siswa tersebut dapat  diurutkan.

Mr. Bubble sangat terkesan dengan apa yang gurunya lakukan. Kejadian itu terukir di benaknya. Bertahun-tahun kemudian, ia membaca sebuah makalah yang ditulis oleh Mr. Selection tentang algoritma sorting yang disebut selection sort. Dia kemudian mengingat metode pengurutan yang dilakukan gurunya dan menyadari bahwa metode tersebut berbeda dengan selection sort. Dia memutuskan untuk mencoba program ini. Dia memprogramnya dan ternyata berhasil.

Selain itu, metode ini juga diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Itulah sebabnya metode ini dinamakan bubble sort (metode gelembung).

2.      Pengertian

Bubble sort adalah metode/algoritma pengurutan dengan cara melakukan penukaran data dengan tepat di sebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut.

3.      Algoritma

Algoritma bubble sort dapat diringkas sebagai berikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:

Ø  Lakukan traversal untuk membandingkan dua elemen berdekatan. Traversal ini dilakukan dari belakang.

Ø  Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan.

Ø  Ulangi langkah di atas untuk struktur data yang tersisa.

Contoh:

Angka 2 1 4 2 3 hendak diurutkan secara ascending

4.      Kura-Kura dan Kelinci pada Bubble Sort

Dalam algoritma Bubble Sort ini, terdapat beberapa ciri khas yang cukup menonjol. Ciri khas dari algoritma ini adalah cepatnya elemen-elemen besar menempati posisi yang tepat dan lambatnya elemen-elemen yang lebih kecil dalam menempati posisi yang tepat. Hal ini dapat ditunjukkan pada contoh data “9 2 4 1” yang akan diurutkan berikut ini menggunakan algoritma Bubble Sort.

Pass Pertama

(9 2 4 1) menjadi (2 9 4 1)

(2 9 4 1) menjadi (2 4 9 1)

(2 4 9 1) menjadi (2 4 1 9)

Pass Kedua

(2 4 1 9) menjadi (2 4 1 9)

(2 4 1 9) menjadi (2 1 4 9)

(2 1 4 9) menjadi (2 1 4 9)

Pass Ketiga

(2 1 4 9) menjadi (1 2 4 9)

(1 2 4 9) menjadi (1 2 4 9)

(1 2 4 9) menjadi (1 2 4 9)

Pass Keempat

(1 2 4 9) menjadi (1 2 4 9)

(1 2 4 9) menjadi (1 2 4 9)

(1 2 4 9) menjadi (1 2 4 9)

Dari proses pengurutan di atas, dapat dilihat bahwa elemen terbesar, “9”, langsung menempati posisi akhir pada pass pertama. Akan tetapi elemen terkecil, “1”, baru menempati posisi pertama pada pass keempat, yaitu pass yang terakhir. Oleh karena itu, muncullah istilah “kura-kura” dan “kelinci” dalam algoritma Bubble Sort. Pada contoh di atas, “1” berperan sebagai “kura-kura”, sedangkan “9” berperan sebagai “kelinci”. Fenomena “kura-kura dan kelinci” ini sering kali mengakibatkan proses pengurutan menjadi lama, terutama elemen “kura-kura”. Hal ini disebabkan oleh “kura-kura” membutuhkan satu kali pass hanya untuk bergeser posisi ke sebelah kiri.

5.      Kelebihan dan Kekurangan

Setiap algoritma memiliki kelebihan dan kekurangannya masing-masing, demikian pula dengan algoritma Bubble Sort. Kelebihan dan kekurangan dari algoritma Bubble Sort dapat dilihat dari karakteristik algoritma Bubble Sort itu sendiri. Berikut ini adalah beberapa kelebihan dan kekurangan dari algoritma Bubble Sort.

      Kelebihan Bubble Sort:

Beberapa kelebihan dari algoritma Bubble Sort adalah sebagai berikut :

·         Algoritma yang simpel.

Hal ini dilihat dari proses pengurutan yang hanya menggunakan rekurensi dan perbandingan, tanpa penggunaan proses lain.

·         Mudah untuk diubah menjadi kode.

Hal ini diakibatkan oleh simpelnya algoritma Bubble Sort, sehingga kecil kemungkinan terjadi kesalahan sintax dalam pembuatan kode.

·         Definisi terurut terdapat dengan jelas dalam algoritma.

Definisi terurut ini adalah tidak adanya satu kalipun swap pada satu kali pass. Berbeda dengan algoritma lain yang seringkali tidak memiliki definisi terurut yang jelas tertera pada algoritmanya.

·         Cocok untuk pengurutan data dengan elemen kecil telah terurut.

      Kekurangan Bubble Sort

Beberapa kekurangan dari algoritma Bubble Sort adalah sebagai berikut :

·         Tidak efektif dalam pengurutan data berskala besar.

·         Langkah pengurutan yang terlalu panjang.

b.      Selection Sort

1.      Sejarah

Ibu Mr. Selection adalah seorang guru bahasa inggris. Tiga bulan sekali, dia membawa pulang kertas ujian untuk dievaluasi. Saat evaluasi selesai, kertas-kertas ujian tersebut disusun di mana nilai tertinggi di susunan pertama dan nilai terendah di susunan terakhir.  Dia memiliki kebiasaan membagi-bagikan kertas ujian tersebut kepada siswa-siswanya sambil memberikan pujian kepada siswa yang memilki nilai tertinggi dan memberikan teguran kepada siswa dengan nilai terendah.

Mr. Selection juga sering diberi tugas oleh ibunya untuk menyusun kertas-kertas ujian. Dia memutuskan untuk menyusun kertas-kertas tersebut dengan mengikuti strategi berikut:

1)      Menempatkan semua lembaran kertas secara bersebelahan.

2)      Mengamati dari kiri ke kanan untuk menemukan kertas siswa yang memperoleh nilai tertinggi.

3)      Mengambil kertas tersebut menempatkannya secara tertelungkup di meja lain.

4)      Mengamati kembali kertas-kertas yang tersisa dari kiri ke kanan dan menemukan kertas dengan nilai tertinggi berikutnya.

5)      Menempatkan kertas tersebut secara tertelungkup di atas kertas yang berada di meja lain.

Sepuluh tahun kemudian, ketika dia harus menulis sebuah program untuk mengurutkan nilai-nilai, dia teringat pada strategi yang pernah dia terapkan dalam penyusunan kertas ujian. Dia kemudian melakukan hal yang sama pada program tersebut dan algoritma tersebut diberi nama selection sort.

2.    Pengertian

Selection sort adalah metode pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.

3.      Algoritma

Algoritma selection sort dapat dirangkum sebagai berikut:

Ø  Temukan nilai yang paling minimum di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.

Ø  Tukar nilai tersebut dengan nilai pada posisi pertama di bagian struktur data yang belum diurutkan.

Ø  Ulangi langkah di atas untuk bagian struktur data yang tersisa.

c.       Insertion Sort

Cara kerja insertion sort sebagaimana namanya. Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen, kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan.  Dari proses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum di-sorting.

Metode insertion sort ini bekerja dengan cara yang serupa dengan apa yang biasa dilakukan oleh seorang pemain kartu professional, yaitu menyisipkan kartu pada suatu lokasi tertentu di bagian yang telah terurut (kita anggap di bagian sebelah kiri). Jika kita menganggap kartu yang berada di tangan (kita anggap di bagian sebelah kiri) merupakan bagian larik yang sudah terurut, dan menganggap “tabel” di sebelah kanan merupakan bagian yang belum terurut, kita akan dapa mengembangkan teknik penguruatan yang dinamakan insertion sort dengan mengambil kartu tertentu dari sebelah kanan kemudian menyisipkannya ke tempat yang sesuai di sebelah kiri.

Algoritma Insertion Sort dapat dirangkum sebagai berikut:

Ø  Simpan nilai Ti kedalam variabel sementara, dengan i = 1.

Ø  Bandingkan nilainya dengan elemen sebelumnya.

Ø  Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).

Ø  Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.

Ø  Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.

Ø  Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).

 

d.      Merge Sort

1.      Sejarah

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Ia adalah seorang ilmuwan yang bekerja di laboratorium penelitian bola basket. Laboratorium tersebut berada jauh dari rumahnya sehingga ia memilih untuk menyewa sebuah tempat yang lebih dekat. Sebelum pindah, dia mengepak semua buku-bukunya ke dalam kardus kecil.

Begitu tiba, dia mengambil buku dan mengaturnya di rak berdasarkan urutan ketinggian buku tersebut. Dia menyadari bahwa jika dia membuka semua kardus dan memilah buku-buku akan sangat  berantakan. Dia memutuskan bahwa ia akan memecahkan masalah ke dalam bit yang lebih kecil. Pertama, dia membuka kardus dan mengatur buku di setiap kardus yang sesuai dengan ukuran tingginya. Setelah diatur, ia menggabungkan kardus-kardus tersebut. Hal itu  membuat pekerjaannya sedikit lebih mudah. Penggabungan elemen-elemen yang diurutkan dari suatu himpunan yang kecil untuk mendapatkan urutan satu himpunan yang lebih  besar adalah lebih mudah daripada mengurutkan seluruh elemen himpunan yang besar bersama-sama. Maka terbentuklah jenis pengurutan data yang disebut merge sort.

2.      Pengertian

Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut:

v  Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.

v  Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut.

3.      Algoritma

Algoritma Merge Sort sederhananya, dapat ditulis berikut:

Ø  Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.

Ø  Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.

Ø  Gabung 2 sublist kembali menjadi satu list terurut.

e.       Quick Sort

 Sejarah

Algoritma quick sort dikembangkan pada tahun 1960 oleh Tony Hoare sementara di Uni Soviet, sebagai mahasiswa tamu di Universitas Negeri Moskow. Saat itu, Hoare bekerja di sebuah proyek penerjemahan mesin untuk National Physical Laboratory. Ia mengembangkan algoritma untuk mengurutkan kata-kata yang akan diterjemahkan, untuk membuat mereka lebih mudah dicocokkan dengan kamus Rusia-ke-Inggris yang sudah disortir yang disimpan pada pita magnetik.

Quick Sort adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini dimuat sebagai artikel di “Computer Journal 5” pada bulan April 1962. Algoritma ini bersifat rekursif, karena kita dapat melihat bahwa masing-masing tumpukan dipecah menjadi tumpukan-tumpukan yang ukurannya semakin kecil, dan proses-proses selanjutnya dilakukan dengan cara serupa namun untuk ukuran tumpukan yang semakin kecil. Quick sort termasuk paradigma algoritma divide and conquer.

Algoritma ini terdiri dari 4 langkah utama:

Ø  Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.

Ø  Ambil sebuah elemen yang akan digunakan sebagai pivot point (poin poros).  (Biasanya elemen yang paling kiri.)

Ø  Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.

Ø  Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.

Kelebihan dan Kelemahan Algoritma Quick Sort

Beberapa hal yang membuat quick sort unggul:

• Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
• Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort.
• Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
• Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

Namun terdapat pula kelemahan quick sort:

• Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
• Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
• Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.

A.      APLIKASI ALGORTIMA SORT

Algoritma sort banyak digunakan pada berbagai aplikasi. Berikut adalah beberapa aplikasi algoritma sort.

• Komersial komputasi organisasi Pemerintah, lembaga keuangan, dan perusahaan komersial mengatur banyak informasi dengan penyortiran. Dari informasi itu account akan diurutkan berdasarkan nama atau nomor, transaksi yang akan diurutkan berdasarkan waktu atau tempat, mail yang akan diurutkan berdasarkan kode pos atau alamat, file yang akan diurutkan berdasarkan nama atau tanggal, atau apa pun, mengolah data tersebut pasti melibatkan algoritma sorting.
• Mencari informasi. Memungkinkan untuk melakukan pencarian yang lebih efisien dengan menggunakan algoritma pencarian biner klasik.
• Riset operasi. Misalkan kita memiliki N pekerjaan untuk menyelesaikan, dimana j pekerjaan membutuhkan t detik _j pengolahan waktu. Kita harus menyelesaikan semua pekerjaan, tapi ingin memaksimalkan kepuasan pelanggan dengan meminimalkan waktu penyelesaian rata-rata dari pekerjaan. Pengolahan waktu terpendek aturan pertama, di mana kita menjadwalkan pekerjaan untuk meningkatkan waktu pemrosesan. Sebagai contoh lain, mempertimbangkan masalah load-balancing, di mana kita memiliki prosesor M identik dan pekerjaan N untuk menyelesaikan, dan tujuan kami adalah untuk menjadwalkan semua pekerjaan pada prosesor sehingga waktu ketika pekerjaan terakhir selesai adalah sedini mungkin . Masalah khusus ini adalah NP-keras jadi kita jangan berharap untuk menemukan cara praktis untuk menghitung jadwal yang optimal. Salah satu metode yang dikenal untuk menghasilkan jadwal yang baik adalah pengolahan aturan waktu terpanjang, di mana kita mempertimbangkan pekerjaan dalam urutan penurunan waktu proses, menetapkan setiap pekerjaan untuk prosesor yang tersedia pertama.
• -Event simulasi. Banyak aplikasi ilmiah melibatkan simulasi, di mana titik perhitungan adalah model dari beberapa aspek dari dunia nyata agar dapat lebih dipahami. Melakukan simulasi tersebut dapat secara efisien memerlukan algoritma yang tepat dan struktur data.
• Simulasi numerik. Komputasi ilmiah ini sering berhubungan dengan akurasi (seberapa dekat kita pada jawaban yang benar?). Akurasi sangat penting ketika kita melakukan jutaan perhitungan dengan nilai-nilai perkiraan seperti representasi floating-point dari bilangan real yang biasa kita gunakan pada komputer. Beberapa algoritma numerik menggunakan antrian prioritas dan menyortir untuk mengontrol akurasi dalam perhitungan.
• Pencarian kombinatorial. Sebuah paradigma klasik dalam kecerdasan buatan adalah untuk mendefinisikan satu set konfigurasi dengan baik didefinisikan bergerak dari satu konfigurasi ke depan dan prioritas yang terkait dengan setiap langkah. Juga pasti adalah konfigurasi awal dan konfigurasi tujuan (yang sesuai dengan telah memecahkan masalah Algoritma A * adalah proses pemecahan masalah di mana kita meletakkan konfigurasi awal pada antrian prioritas, kemudian melakukan hal berikut sampai mencapai tujuan. Menghapus konfigurasi tertinggi-prioritas dan menambah antrian semua konfigurasi yang dapat dicapai dari yang dengan satu gerakan (tidak termasuk yang baru saja dihapus).

B.       KESIMPULAN

Algoritma pengurutan yang mudah dalam hal implementasi adalah Bubble Sort, Selection Sort, dan Insertion Sort. Bubble sort merupakan algoritma yang paling mudah dan memiliki definisi terurut yang jelas dalam algoritmanya. Algoritma ini juga memiliki ciri khas, yaitu “kura-kura dan kelinci”, namun merrupakan algoritma yang berjalan paling lambat. Insertion sort merupakan algoritma yang paling efisien.

Merge sort dan quick sort dapat diterapkan untuk data yang berjumlah sangat banyak sehingga lebih baik jika dibandingkan dengan ketiga algoritma yang lain.  Quick sort adalah algortima yang tercepat. Dalam situasi yang paling praktis, quick sort dapat menjadi metode pilihan. Namun, jika stabilitas adalah penting dan ruang yang tersedia, merge sort mungkin yang terbaik.