Pengertian dan Metode Quick Sort

1.      METODE QUICK SORT

            Algoritma quicksort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di Computer Journal 5 pada April 1962. Bentuknya yang sederhana, efisien dan efektif dengan cepat membuatnya menjadi algoritma pengurutan (sorting) yang paling banyak digunakan, terutama dalam bahasa pemrograman. Berbagai penelitian dan pengembangan telah banyak dilakukan hingga saat ini. Tercatat peneliti seperti Sedgewick, Bentley, McIlroy, Clement, Flajolet, Vallee, hingga Martinez, membuat analisis dan implementasi dari quicksort.

Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif.Sangat 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.

            Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data,  kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa            Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini mempunyai efektifitas yang tinggi dengan teknik menukarkan dua elemen dengan jarak yang cukup besar. Metode pengurutan quick sort dapat diimplementasikan dalam bentuk non rekursif dan rekursif

            Berbagai varian dari quicksort pada intinya berupaya untuk mengembangkan teknik-teknik pembuatan partisi yang efektif untuk berbagai macam masukan.Hal ini merupakan bahan yang terus dipelajari hingga kini.Ditambah pula dengan perbaikan dari segi pemrograman sehingga lebih efisien (seperti mengurangi operasi pembandingan, pertukaran maupun perulangan).

            Pada tahun 1998 M.D. McIlroy membuat tulisan berjudul “A Killer Adversary for Quicksort” yang menguraikan cara untuk membuat susunan data tertentu (dalam array) hingga operasi pengurutan menggunakan quicksort mendekati kuadratik O(n2). Cara ini berlaku untuk setiap varian dari quicksort dengan syarat tertentu.Dikenal juga dengan istilah antiqsort.

A.   ALGORITMA QUICKSORT

       1.  Divide and Conquer

          Divide and conquer adalah metode pemecahan masalah yang bekerja dengan membagi (divide) masalah menjadi beberapa sub-masalah yang sama atau berhubungan, hingga masalah tersebut menjadi sederhana untuk dipecahkan (conquer) secara langsung. Pemecahan dari tiap-tiap sub-masalah kemudian digabungkan untuk memberikan solusi terhadap masalah semula.

          Metode divide and conquer menawarkan penyederhanaan masalah dengan pendekatan tiga langkah sederhana: pembagian masalah menjadi sekecil mungkin, penyelesaian masalah-masalah yang telah dikecilkan, kemudian digabungkan kembali untuk mendapat solusi optimal secara keseluruhan. Khusus untuk quicksort, proses penggabungan (combine) tidak perlu dilakukan, karena sudah terjadi secara alami.

          Dalam penerapannya metode ini dilakukan secara rekursif, yaitu memanggil dirinya sendiri. Cara pemanggilan ini memanfaatkan mekanisme stack dalam menyimpan data yang sedang diproses. Namun bisa juga dengan versi non-rekursif yaitu dengan membuat struktur data tertentu yang meniru cara kerja stack.

       2. Algoritma

Prinsip dalam algoritma quicksort sebagai berikut (diuraikan pula oleh Sedegwick):

·         Bila elemen dalam array kurang dari jumlah tertentu (biasanya 2), proses selesai.

·         Ambil sebuah elemen yang berfungsi sebagai poros.

·         Pisahkan array dalam 2 bagian, sebelah kiri lebih kecil dari poros, sebelah kanan lebih besar dari poros.

·         Ulangi proses secara rekursif pada tiap-tiap bagian.

Hal penting dari hal algoritma ini adalah: bagaimana memilih poros dengan tepat dan secara efisien mengatur tiap-tiap elemen sehingga didapat elemen kecil > poros > elemen besar dalam kondisi (mendekati) seimbang.

3. Kompleksitas

          Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai poros.Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian sub-masalah.

B.   PROGRAM PENDUKUNG

          Untuk membantu pengujian dibuatlah sebuah program khusus[7]. Baik program maupun penerapan algoritma quicksort menggunakan bahasa Object Pascal, khususnya menggunakan Borland Delphi.Bahasa Pascal mudah dimengerti dan cukup mewakili dalam penulisan algoritma.

1. Class TQuickSort

     Untuk menyeragamkan penulisan tiap-tiap algoritma, dibuat sebuah common class, yaitu TQuickSort.Class ini berisi fungsi-fungsi yang ada dalam tiap-tiap algoritma quicksort dan melakukan pencatatan statistik tiap kali dipanggil. Berikut isi rutin-rutin tersebut:

·         Compare (X, Y), yaitu membandingkan X dan Y dengan hasil negatif bila lebih kecil, 0 bila sama, dan positif bila lebih besar.

·         Exchange (X, Y), yaitu menukar variabel pada posisi X dan Y.

·         CheckStack, yaitu mengecek banyaknya pemanggilan diri sendiri (rekursif) yang dilakukan. Pengecekan ini dengan melihat posisi stack (ESP), apabila berbeda dari posisi sebelumnya maka kedalaman rekursif telah bertambah.

·         Sort, yaitu fungsi publik yang melakukan operasi pengurutan. Sebelumnya array masukan disalin ke buffer internal, memanggil fungsi quicksort, dan mengecek hasil apakah telah urut. Keluaran dari fungsi ini berupa string statistik hasil.

·         AntiSort, yaitu fungsi publik untuk mengisi array dengan susunan angka sesuai algoritma antiqsort. Hasil array ini akan diurutkan kembali tahap berikutnya.

Setiap implementasi algoritma quicksort diturunkan dari class TQuickSort, dengan mendefinisikan ulang (override) prosedur abstrak quicksort. Ketika dijalankan (fungsi Sort), setiap algoritma yang didaftarkan akan dipanggil dan hasilnya ditampilkan dalam TMemo.

C.   PERCOBAAN DAN ANALISA

          Menggunakan class TQuickSort, yang diturunkan dalam bermacam-macam algoritma, dilakukan pengujian unjuk kerja. Hal-hal yang dipantau adalah:

·         Pembandingan, yaitu berapa banyak terjadi pembandingan antara 2 elemen. Setiap operasi pembandingan, baik dalam mencari elemen ataupun poros, akan dicatat.

·         Penukaran, yaitu berapa banyak terjadi pertukaran antara 2 elemen.

·         Rekursif, yaitu berapa dalam terjadi pemanggilan stack (dalam proses rekursif).

·         Waktu, yaitu berapa lama (dalam milidetik) suatu algoritma berjalan. Waktu yang dibutuhkan suatu algoritma tidak selalu berbanding lurus dengan operasi pembandingan, pertukaran, maupun rekursif.

       Akibat pengembangan quicksort sudah sedemikian rupa, sehingga asal-usul dan bentuk algoritma tidak diketahui asalnya.Dalam hal ini hanya diambil beberapa contoh quicksort yang dianggap cukup mewakili sebagai percobaan.

       Dalam melakukan pengambilan waktu tidak dilakukan hasil rata-rata, melainkan pada 1x hasil saja. Hal ini disebabkan pengambilan contoh (sampling) array sudah cukup mewakili, yaitu 1.000.000 angka Integer (4 byte), kecuali 10.000 angka untuk algoritma (partisi) Lomuto dan antiqsort.

v  Beberapa hal yang membuat quicksort unggul:

·      Secara umum memiliki kompleksitas O(n log n).

·      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 mergesort dan heapsort.

·      Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.

·      Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter). 

v  Namun terdapat pula kelemahan quicksort:

·         Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).

·         Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).

·         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.

·         Pada bahasa pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class TList dan TStringList dalam Delphi (Object Pascal) maupun FreePascal.

Contoh Quick Sort:

Tweet