Quicksort

**Quicksort** merupakan Algoritme pengurutan yang dikembangkan oleh Tony Hoare. performa rata-rata pengurutan O(*n*&nbsp;log&nbsp;*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. Quicksort sering lebih cepat dalam praktiknya daripada algoritma urut gabung dan heapshort. 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&nbsp;*n*).

Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.

## Algoritma
Quicksort merupakan *Algoritma Pembagi*. Pertama quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil: element kecil dan element besar. Quicksort kemudian dapat menyortir sub list itu secara rekursif.

Langkah-Langkah pengerjaannya ialah:
# Ambil sebuah elemen, yang disebut dengan *pivot*, pada sebuah daftar.
# Urutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut **Partition**.
# Sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar.

Kasus dasar dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di sorting.

### Versi Sederhana
Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut:


```javascript
function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls
```


Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan membandingkan mereka pada elemen yang lain. Prosedur ini disebuk *Sorting Pembandingan*. Jenis ini juga merupakan jenis *sorting yang stabil* (asumsikan bahwa *untuk setiap* method menerima elemen pada urutan aslinya dan pivot yang dipilih merupakan elemen terakhir dari nilai yang sama).

Kebenaran dari algoritma partisi didasari pada dua argumen berikut:
* Pada setiap iterasi, seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot (**Invarian Loop**).

Kebenaran dari keseluruhan algortima dapat dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, algoritma tidak akan mengubah data; untuk jumlah data yang lebih besar, algoritma akan menghasilkan dua bagian, elemen yang kurang dari pivot dan elemen yang lebih besar dari nya, data ini sendiri akan diurutkan secara hipotesis rekursif.

### Versi In-place
Kerugian dari versi sederhana diatas membutuhkan ruang simpan O(*n*) yang lebih besar, yang sama buruknya seperti **merge sort**. Memory tambahan yang dibutuhkan dapat juga secara radikal berpengaruh pada kecepatan dan performa cache pada implementasi praktiknya. Terdapat juga versi yang lebih rumit yang menggunakan algoritma partisi **in-place** dan dapat mencapai urutan lengkap menggunakan ruang O(log*n*) (tidak dihitung input) pada rata-rata (untuk sekali pemanggilan tumpukan). Kita mulai dengan fungsi partisi: