Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• Kasus Rata-rata: O(n log n)
  • Pivot yang seimbang membagi array menjadi dua bagian yang kira-kira sama besar setiap kali, sehingga menghasilkan sekitar log n tingkat proses partisi dengan pekerjaan O(n).
• Kasus Terburuk: O(n²)
  • Jika pivot selalu berupa elemen terkecil atau terbesar (misalnya, array yang sudah terurut dengan elemen terakhir sebagai pivot), salah satu sisi akan selalu kosong dan rekursi akan mencapai kedalaman n tingkat.

Kompleksitas Ruang:

• O(n) untuk versi yang kita buat di sini, karena kita membuat list baru yang lebih kecil dan lebih besar di setiap langkah. Quick Sort klasik yang in-place meningkatkan efisiensi ini sehingga hanya menggunakan ruang tambahan O(log n).

Ringkasan:

• Quick Sort sangat cepat secara rata-rata dan menjadi algoritma pengurutan andalan dalam praktik.
• Pemilihan pivot yang buruk dapat membuat kompleksitasnya menjadi O(n²), strategi pemilihan pivot yang baik (seperti memilih elemen secara acak atau memilih median) dapat menghindari hal ini.