Creator Media

Pengertian Algoritma Quick Sort

Quicksort merupakan Algoritma Sorting yang dikembangkan oleh C.A.R Hoare pada tahun1960 yang secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting pergantian pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n 2 ), walaupun kejadian seperti ini sangat langka. Quick sort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).

Pada masalah pengurutan data bilangan bulat (integer) secara terindeks pada suatu list atau array dari bilangan yang paling besar sampai ke bilangan yang paling kecil atau sebaliknya. Tidak hanya dapat diterapkan pada pengindeksan bilangan saja, namun juga untuk pengindeksan huruf (abjad) dari A ke Z atau sebaliknya. Algoritma ini sangat baik diterapkan pada kasus pengindeksan kumpulan kata (library sort utility) atau kumpulan bilangan atau kombinasinya.

Menurut Saputra, dkk (2010:1) menjelaskan bahwa Quick Sort adalah sebuah algoritma sorting dari model Divide and Conquer yaitu dengan cara mereduksi tahap demi tahap sehingga menjadi 2 bagian yang lebih kecil.

Quick Sort merupakan algoritma yang sangat cepat dibandingkan dengan algirtma sorting lainnya, karena algoritma quick sort ini melakukan sorting dengan membagi masalah menjadi sub masalah dan sub masalah dibagi lagi menjadi sub-sub masalah sehingga sorting tersebut menjadi lebih cepat walaupun memakan ruang memori yang besar

Pada sumber lain juga menyebutkan bahwa Quicksort merupakan algoritma sorting yang dikembangkan oleh Tony Hoare pada tahun 1962. Algoritma ini juga dikenal sebagai partitionexchange sort (sorting pembagian pembagi). Algoritma quicksort termasuk dalam algoritma yang sulit membagi, mudah menggabung (hard split / easy join).

Quick sort juga disebut juga dengan partition Exchange sort. Disebut Quick Sort, karena terbukti mempunya ‘average behaviour’ yang terbaik di antara metoda pengurutan yang ada. Disebut Partition Exchange Sort karena konsepnya membuat partisi-partisi, dan sort dilakukan per partisi.

Algoritma quicksort bekerja menurut prinsip bagi-dan-pecahkan (divide-and-conquer). Dengan demikian hal mendasar dalam algoritma quicksort adalah pemilihan poros (pivot) dan pembuatan partisi sedemikian rupa sehingga elemen dengan nilai kecil ada di bagian kiri poros dan elemen dengan nilai besar ada di bagian kanan poros.

Berbagai varian dari quicksort pada intinya berupaya untuk mengembangkan teknikteknik 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).

Teknik mempartisi tabel sebagai berikut :

• • Pilih x ∈ { A1, A2, …, An} sebagai elemen pivot
  • Pindai tabel dari kiri sampai ditemukan elemen Ap ≥ x
  • Pindai tabel dari kanan sampai ditemukan elemen Aq ≤ x
  • Pertukarkan Ap ⇔Aq
  • Ulangi point kedua, dari posisi p + 1, dan point ketiga, dari posisi q – 1 sampai kedua pemindaian bertemu di tengah tabel

Sistem algoritma Quick Sort sendiri adalah membagi kumpulan suatu data menjadi beberapa sub bagian/partisi. Pembagian partisi ini berdasarkan letak dari suatu pivot yang dapat dipilih secara acak. Akan tetapi justru penentuan pivot inilah yang sangat mempengaruhi dalam proses kecepatan sorting. Pemilihan pivot bisa dengan berbagai cara. Bisa dari elemen pertama, elemen tengah, elemen terakhir atau secara acak. Cara yang diangap paling bagus dan lazim adalah pemilihan pivot pada elemen tengah dari suatu tabel. Karena dengan memilih elemen tengah, tabel tersebut akan dibagi menjadi 2 partisi yang sama besar. Penentuan elemen tengah dapat dirumuskan sebagai berikut :

Pivot = a [(indeks awal + indeks akhir) div 2]

Langkah-langkah mempartisi tabel dalam Quick Sort adalah sebagai berikut :

1. Pilih x {a1, a2, …, an} sebagi elemen pivot.
2. Pindai (scan) tabel dari kiri sampai ditemukan elemen ap ≥ x 3)
3. Pindai tabel dari kanan sampai ditemukan elemen aq ≤ x 4)
4. Pertukarkan ap dan aq 5)
5. Ulangi langkah 2 dari posisi p+1, dan langkah 3 dari posisi q-1, sampai kedua pemindaian bertemu di tengah tabel

Pembahasan lainnya :

1. 1. Kompleksitas Algoritma Quick Sort
   2. Langkah-Langkah Algoritma Quick Sort
   3. Rangkuman Algoritma Divide and Conquer
   4. Langkah-Langkah Algoritma Bucket Sorting
   5. Cara Memilih Pivot dalam Algoritma Quick Sort
   6. Kelebihan dan Kekurangan Algoritma Quick Sort

Originally posted 2022-10-11 23:42:03.