# Quicksort

Adres: https://softwaredictionary.org/tr/terimler/quicksort
Kategori: Veri Yapıları
Son güncelleme: 2026-09-30
Türkçe karşılığı: hızlı sıralama
Okunuşu: kuiksort

Kısaca: Quicksort, öğeleri seçilen bir pivot etrafında bölümleyen, sonra küçük ve büyük grupları aynı şekilde sıralayan bir böl ve yönet sıralama algoritmasıdır.

## Quicksort nedir?

Quicksort, bir öğeyi pivot olarak seçen, listeyi pivottan küçük her şey onun önüne, büyük her şey arkasına gelecek biçimde yeniden düzenleyen ve sonra bu iki parçayı aynı şekilde sıralayan bir sıralama algoritmasıdır. Bölümlemeden sonra pivot zaten nihai konumundadır; bu yüzden birleştirme adımına gerek yoktur. 1959'da Tony Hoare tarafından geliştirilmiştir ve pratikte hâlâ en hızlı genel amaçlı sıralama algoritmalarından biridir.

Ortalamada quicksort O(n log n) sürede çalışır, çünkü makul bir pivot öğeleri kabaca ikiye böler ve her bölümleme seviyesi n öğeyi işler. En kötü durum O(n^2)'dir ve pivot tekrar tekrar en küçük ya da en büyük öğe olduğunda gerçekleşir; örneğin her zaman ilk öğeyi seçen saf bir sürüme zaten sıralı veri verildiğinde. Uygulamalar bunu rastgele bir pivot ya da üç öğenin ortancasını seçerek önler. Bölümleme öğeleri dizinin kendi içinde takas ettiği için quicksort yerinde sıralar ve önce küçük parçayı ele aldığında özyineleme için yalnızca O(log n) ek bellek gerektirir.

Bir sınıfı boya göre sıralamayı düşünün: bir öğrenci seçin, ondan kısa olan herkesi sola, uzun olan herkesi sağa gönderin, sonra her grup bir kişi olana kadar her grupta tekrarlayın. Quicksort'un küçük bellek ayak izi ve komşu öğelere önbellek dostu erişimi onu yaygın bir varsayılan yapar. Quicksort ile başlayan ve özyineleme çok derinleşirse heap sort'a geçen melez bir yöntem olan introsort, C++'ın `std::sort` fonksiyonunun birçok uygulamasında kullanılır; Java ise ilkel değerlerden oluşan dizileri çift pivotlu bir quicksort ile sıralar. Aynı bölümleme fikri, k. en küçük öğeyi, örneğin medyanı, ortalama O(n) sürede bulan quickselect'i de çalıştırır.

Quicksort en sık merge sort ile karşılaştırılır. Merge sort O(n log n) garanti eder ve kararlıdır, ancak diziler için O(n) ek bellek gerektirir; quicksort yerinde sıralar ve pratikte genellikle daha hızlıdır, ama en kötü durumu O(n^2)'dir ve kararlı değildir; bu yüzden eşit öğelerin göreli sırası değişebilir. Kısacası quicksort işini bölerken, yani bölümlemeyle; merge sort ise birleştirirken, yani birleştirmeyle yapar.

## Önemli noktalar

- Quicksort öğeleri bir pivot etrafında bölümler, sonra her tarafı özyinelemeyle sıralar.
- Ortalamada O(n log n) sürer, ancak en kötü durumu O(n^2)'dir.
- Rastgele ya da üçün ortancası pivot, en kötü durumu çok düşük olasılıklı yapar.
- Az ek bellekle yerinde sıralar, ancak kararlı değildir.
- Introsort gibi melezler, O(n log n) garantisi için quicksort ile heap sort'u birleştirir.

## Örnek: Python'da kısa ve okunaklı bir quicksort

```python
import random

def quicksort(items):
    if len(items) <= 1:
        return items  # base case: nothing left to sort
    pivot = random.choice(items)  # a random pivot makes the O(n^2) case unlikely
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    # The pivot group is already in its final place; sort each side the same way
    return quicksort(smaller) + equal + quicksort(larger)

print(quicksort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]
# Production versions partition in place instead of building new lists
```

## Sık sorulan sorular

**En kötü durumu O(n^2) olan quicksort neden hızlı?**

Rastgele ya da üçün ortancası bir pivotla en kötü durum son derece düşük olasılıklıdır ve ortalama durum küçük sabit çarpanlarla O(n log n)'dir. Quicksort ayrıca komşu bellekte yerinde çalışır; bu da CPU önbelleğinden iyi yararlanır.

**Quicksort kararlı mıdır?**

Hayır, standart yerinde sürüm kararlı değildir, çünkü bölümleme eşit öğeleri birbirinin üzerinden takas edebilir. Eşit öğelerin özgün sırasını koruması gerekiyorsa merge sort ya da Timsort gibi kararlı bir kütüphane sıralaması kullanın.

**Quicksort ile merge sort arasındaki fark nedir?**

İkisi de ortalamada O(n log n) olan böl ve yönet sıralamalarıdır. Quicksort bir pivot etrafında bölümler ve yerinde sıralar, ancak O(n^2)'ye düşebilir ve kararlı değildir; merge sort ise eşit böler, her zaman O(n log n) sürede çalışır, kararlıdır ve O(n) ek bellek gerektirir.

---

Software Dictionary: https://softwaredictionary.org/tr · https://softwaredictionary.org/tr/llms.txt