Time and Space Complexity

Zaman Karmaşıklığı:

• Ortalama Durum: O(n log n)
  • Dengeli bir pivot, diziyi her seferinde kabaca ikiye böler ve yaklaşık log n seviyeli O(n) bölüştürme (partitioning) işi sağlar.
• En Kötü Durum: O(n²)
  • Eğer pivot her zaman en küçük veya en büyük eleman ise (örneğin, son elemanı pivot olan zaten sıralanmış bir dizi), bir taraf her seferinde boş kalır ve özyineleme (recursion) n seviye derinliğine ulaşır.

Alan Karmaşıklığı:

• Burada oluşturduğumuz sürüm için O(n), çünkü her adımda yeni küçük ve büyük listeler oluşturuyoruz. Klasik in-place (yerinde) Quick Sort, bunu O(log n) ek alana iyileştirir.

Özet:

• Quick Sort ortalamada çok hızlıdır ve pratikte tercih edilen bir sıralama algoritmasıdır.
• Kötü bir pivot seçimi onu O(n²) seviyesine düşürebilir; iyi pivot stratejileri (rastgele veya medyan bir eleman seçmek gibi) bundan kaçınır.