DAA - Sortir Cepat

Ini digunakan berdasarkan prinsip divide-and-conquer. Pengurutan cepat adalah algoritme pilihan dalam banyak situasi karena tidak sulit untuk diterapkan. Ini adalah jenis tujuan umum yang baik dan mengkonsumsi sumber daya yang relatif lebih sedikit selama eksekusi.

Keuntungan

Ini ada di tempatnya karena hanya menggunakan tumpukan tambahan kecil.
Itu hanya membutuhkan n (log n) waktu untuk menyortir n item.
Ini memiliki loop dalam yang sangat pendek.
Algoritme ini telah menjalani analisis matematis menyeluruh, pernyataan yang sangat tepat dapat dibuat tentang masalah kinerja.

Kekurangan

Ini rekursif. Apalagi jika rekursi tidak tersedia, implementasinya sangat rumit.
Ini membutuhkan waktu kuadrat (yaitu, n2) dalam kasus terburuk.
Ini rapuh, yaitu kesalahan sederhana dalam implementasi dapat luput dari perhatian dan menyebabkannya berkinerja buruk.

Pengurutan cepat bekerja dengan mempartisi larik yang diberikan A[p ... r] menjadi dua sub larik yang tidak kosong A[p ... q] dan A[q+1 ... r] sedemikian rupa sehingga setiap kunci masuk A[p ... q] kurang dari atau sama dengan setiap tombol masuk A[q+1 ... r].

Kemudian, dua sub-array diurutkan berdasarkan panggilan rekursif ke Quick sort. Posisi pasti dari partisi tersebut bergantung pada larik dan indeks yang diberikanq dihitung sebagai bagian dari prosedur partisi.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Perhatikan bahwa untuk mengurutkan seluruh larik, panggilan awal harus Quick-Sort (A, 1, length[A])

Sebagai langkah pertama, Quick Sort memilih salah satu item dalam larik untuk diurutkan sebagai pivot. Kemudian, array tersebut dipartisi di kedua sisi pivot. Elemen yang lebih kecil dari atau sama dengan poros akan bergerak ke kiri, sedangkan elemen yang lebih besar atau sama dengan poros akan bergerak ke arah kanan.

Mempartisi Array

Prosedur partisi mengatur ulang sub-array di tempat.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Analisis

Kompleksitas kasus terburuk dari algoritma Quick-Sort adalah O(n²). Namun dengan menggunakan teknik ini, dalam kasus rata-rata umumnya kita mendapatkan keluarannyaO(n log n) waktu.