---
title: 'Kabarcık, Seçmeli ve Eklemeli Sıralama'
source: 'https://academia.sh/tr/kurslar/algoritmalar/temel-siralamalar'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:39+00:00'
license: 'CC BY-SA 4.0'
---

# Kabarcık, Seçmeli ve Eklemeli Sıralama

Sıralama probleminin tanımı, kararlılık ve yerinde çalışma ölçütleri, üç karesel algoritmanın karşılaştırma ve taşıma maliyetleri, ters çift sayısı.

İkili arama sıralılık varsayıyordu; öyleyse sıralamanın kendisi incelenmelidir. Sıralama,
algoritma öğretiminin merkezinde durur: aynı problem, farklı fikirlerle onlarca kez
çözülmüş ve çözümler tam olarak bu kursun araçlarıyla karşılaştırılmıştır.

Bu ders karesel maliyetli üç temel algoritmayı ele alır. Amaç yalnızca onları öğrenmek
değil, sonraki derslerin daha iyi algoritmalarını karşılaştıracak bir taban kurmaktır.

## Problem ve Ölçütler

**Sıralama problemi:** Girdi, karşılaştırılabilir elemanlardan oluşan bir dizidir. Çıktı,
aynı elemanların bir **permütasyonu** olan ve azalmayan sırada dizilmiş bir dizidir.

İki koşul da gereklidir. Yalnızca sıralılık istenirse, girdiyi silip boş dizi döndürmek
"çözüm" sayılırdı; permütasyon koşulu bunu engeller.

Sıralama algoritmaları üç ölçütle ayrılır:

**Kararlılık (stability).** Eşit anahtarlı elemanların göreli sırası korunuyorsa algoritma
kararlıdır. Çok anahtarlı sıralamalarda belirleyicidir: önce şehre, sonra kararlı bir
algoritmayla tarihe göre sıralanan kayıtlarda şehir sırası bozulmaz.

**Yerinde çalışma.** Ek alan sabitse algoritma yerindedir.

**Uyarlanabilirlik.** Girdi kısmen sıralıysa maliyeti düşüyorsa algoritma uyarlanabilirdir.

Ayrıca iki ayrı maliyet sayılır: **karşılaştırma** sayısı ve **taşıma** (yer değiştirme
veya kaydırma) sayısı. Elemanlar büyük nesnelerse taşıma pahalıdır; karşılaştırma karmaşık
bir işlevse karşılaştırma pahalıdır.

## Kabarcık Sıralama

Komşu elemanlar karşılaştırılır ve sıra bozuksa yer değiştirilir. Her geçişte en büyük
eleman sona "kabarır".

```python
def kabarcik_siralama(dizi: list[int]) -> list[int]:
    """Değişmez: her dış turdan sonra son `n - son` eleman kesin yerindedir."""
    d = list(dizi)
    for son in range(len(d) - 1, 0, -1):
        degisim = False
        for i in range(son):
            if d[i] > d[i + 1]:
                d[i], d[i + 1] = d[i + 1], d[i]
                degisim = True
        if not degisim:                 # hiç değişim yoksa dizi sıralıdır
            break
    return d


print(kabarcik_siralama([5, 2, 9, 1, 5, 6]))    # [1, 2, 5, 5, 6, 9]
```

Erken çıkış bayrağı olmadan algoritma her durumda $n(n-1)/2$ karşılaştırma yapar. Bayrakla
birlikte sıralı girdide tek geçişte durur: en iyi durum $O(n)$ olur.

En kötü ve ortalama durum $O(n^2)$'dir. Taşıma sayısı da karesel olabilir — ters sıralı
girdide her karşılaştırma bir yer değiştirmeye yol açar. Algoritma kararlıdır (yalnızca
kesin büyüklükte yer değiştirilir) ve yerindedir.

## Seçmeli Sıralama

Kalan bölümün en küçüğü bulunur ve bulunduğu yerle sınırın başı yer değiştirir.

```python
def secmeli_siralama(dizi: list[int]) -> list[int]:
    """Değişmez: her turdan sonra ilk i eleman kesin sıralıdır."""
    d = list(dizi)
    for i in range(len(d) - 1):
        en_kucuk = i
        for j in range(i + 1, len(d)):
            if d[j] < d[en_kucuk]:
                en_kucuk = j
        d[i], d[en_kucuk] = d[en_kucuk], d[i]
    return d


print(secmeli_siralama([5, 2, 9, 1, 5, 6]))     # [1, 2, 5, 5, 6, 9]
```

Karşılaştırma sayısı girdiden bağımsızdır: her zaman $n(n-1)/2$. Uyarlanabilir değildir —
sıralı girdide de tam maliyeti öder.

Buna karşılık **taşıma sayısı en çok $n-1$**'dir ve bu, algoritmanın tek üstünlüğüdür:
elemanlar çok büyükse veya yazma işlemi pahalıysa (bazı kalıcı bellek türlerinde okuma ile
yazma maliyeti eşit değildir), az yazma yapan bir algoritma tercih edilebilir.

Bu biçimiyle kararlı **değildir**: uzak bir elemanla yer değiştirme, eşit anahtarlıların
sırasını bozabilir.

```python
def secmeli_siralama_kayit(kayitlar: list[tuple[int, str]]) -> list[tuple[int, str]]:
    """Yalnızca ilk alana (anahtara) göre sıralar; ikinci alan kimliktir."""
    d = list(kayitlar)
    for i in range(len(d) - 1):
        en_kucuk = i
        for j in range(i + 1, len(d)):
            if d[j][0] < d[en_kucuk][0]:
                en_kucuk = j
        d[i], d[en_kucuk] = d[en_kucuk], d[i]
    return d


print(secmeli_siralama_kayit([(2, "a"), (2, "b"), (1, "c")]))
# [(1, 'c'), (2, 'b'), (2, 'a')]
```

Çıktıda `b`, `a`'nın önüne geçmiştir; girdide sıra tersineydi. Yer değiştirme yerine
kaydırma yapan bir değişke kararlı olur, ama o zaman taşıma üstünlüğü kaybolur.

## Eklemeli Sıralama

Her eleman, kendisinden önceki sıralı bölüme doğru yerine kaydırılarak eklenir. İskambil
kâğıtlarını elde sıralama biçimi budur.

```python
def eklemeli_siralama(dizi: list[int]) -> list[int]:
    """Değişmez: her turun başında ilk i eleman kendi arasında sıralıdır."""
    d = list(dizi)
    for i in range(1, len(d)):
        anahtar = d[i]
        j = i - 1
        while j >= 0 and d[j] > anahtar:
            d[j + 1] = d[j]             # kaydır
            j -= 1
        d[j + 1] = anahtar
    return d


def eklemeli_siralama_kayit(kayitlar: list[tuple[int, str]]) -> list[tuple[int, str]]:
    d = list(kayitlar)
    for i in range(1, len(d)):
        anahtar = d[i]
        j = i - 1
        while j >= 0 and d[j][0] > anahtar[0]:
            d[j + 1] = d[j]
            j -= 1
        d[j + 1] = anahtar
    return d


print(eklemeli_siralama([5, 2, 9, 1, 5, 6]))    # [1, 2, 5, 5, 6, 9]
print(eklemeli_siralama_kayit([(2, "a"), (2, "b"), (1, "c")]))
# [(1, 'c'), (2, 'a'), (2, 'b')]   — girdideki a, b sırası korundu
```

Döngü koşulundaki `>` işareti kararlılığın kaynağıdır: eşitlikte kaydırma durur, yeni
eleman eşitinin arkasına yerleşir. `>=` yazılsaydı algoritma kararlılığını yitirirdi.

En iyi durum sıralı girdidir: iç döngü hiç çalışmaz, maliyet $O(n)$. En kötü durum ters
sıralı girdidir: $n(n-1)/2$ kaydırma, $O(n^2)$. Ortalama durumda her eleman sıralı bölümün
yarısı kadar kayar; yine karesel ama sabiti küçüktür.

## Ters Çift Sayısı

Eklemeli sıralamanın maliyeti, girdinin "ne kadar bozuk" olduğuyla tam olarak
ölçülebilir.

**Ters çift (inversion)**, $i < j$ iken $d_i > d_j$ olan çiftlerdir. Sıralı dizide sıfır,
ters sıralı dizide $n(n-1)/2$ tanedir.

Eklemeli sıralamanın yaptığı her kaydırma tam olarak bir ters çifti giderir; dolayısıyla
toplam kaydırma sayısı ters çift sayısına eşittir ve maliyet $O(n + \text{ters çift})$
olur.

```python
def ters_cift_sayisi(dizi: list[int]) -> int:
    return sum(1 for i in range(len(dizi))
                 for j in range(i + 1, len(dizi)) if dizi[i] > dizi[j])


def eklemeli_kaydirma_sayisi(dizi: list[int]) -> int:
    d, sayac = list(dizi), 0
    for i in range(1, len(d)):
        anahtar, j = d[i], i - 1
        while j >= 0 and d[j] > anahtar:
            d[j + 1] = d[j]
            j -= 1
            sayac += 1
        d[j + 1] = anahtar
    return sayac


for ornek in ([1, 2, 3, 4, 5], [5, 2, 9, 1, 5, 6], [5, 4, 3, 2, 1]):
    print(ornek, ters_cift_sayisi(ornek), eklemeli_kaydirma_sayisi(ornek))

# [1, 2, 3, 4, 5] 0 0
# [5, 2, 9, 1, 5, 6] 6 6
# [5, 4, 3, 2, 1] 10 10
```

İki sütunun her satırda eşit olması rastlantı değildir; algoritmanın ne yaptığının tam
tanımıdır. Sonuç pratikte önemlidir: **neredeyse sıralı** veride eklemeli sıralama
doğrusala yakın çalışır. Sıralı bir kütüğe birkaç yeni kayıt eklenmiş bir dizi bu
tanıma girer.

## Karşılaştırma

| Ölçüt | Kabarcık | Seçmeli | Eklemeli |
|---|---|---|---|
| En iyi durum | $O(n)$ (bayrakla) | $O(n^2)$ | $O(n)$ |
| Ortalama / en kötü | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Taşıma sayısı | $O(n^2)$ | $O(n)$ | $O(n^2)$ |
| Kararlı | Evet | Hayır | Evet |
| Yerinde | Evet | Evet | Evet |
| Uyarlanabilir | Evet | Hayır | Evet |

Üçü de karesel sınıftadır; aralarındaki fark sabitlerde ve ikincil ölçütlerdedir. Pratikte
eklemeli sıralama, küçük dizilerde ve neredeyse sıralı veride öne çıkar — bu nedenle
gelişmiş sıralama gerçekleştirimleri, küçük parçalarda ona geçer.

Kabarcık sıralamanın belirgin bir üstünlüğü yoktur; öğretici değeri, komşu takas fikrinin
en yalın hâli olmasıdır.

## Özet

- Sıralama problemi iki koşul ister: çıktı sıralı olmalı ve girdinin bir permütasyonu
  olmalıdır.
- Algoritmalar kararlılık, yerinde çalışma ve uyarlanabilirlik ölçütleriyle ayrılır;
  karşılaştırma ve taşıma sayıları ayrı sayılır.
- Kabarcık sıralama komşu takasla çalışır; erken çıkış bayrağı en iyi durumu doğrusala
  indirir.
- Seçmeli sıralama her zaman karesel karşılaştırma yapar ama doğrusal sayıda taşıma
  yapar; bu biçimiyle kararlı değildir.
- Eklemeli sıralama kararlı, yerinde ve uyarlanabilirdir; kaydırma sayısı ters çift
  sayısına eşittir.
- Üçü de karesel sınıftadır; fark sabitlerde ve ikincil ölçütlerdedir.

## Sonraki Adım

Karesel sınıf, ölçek büyütme tablosunun gösterdiği gibi milyonluk verilerde
kullanılamazdı. Sonraki ders, karmaşıklık hesabı dersinde bağıntısı çözülen böl ve yönet
fikrini sıralamaya uygular: birleştirmeli sıralama, $O(n \log n)$ güvencesini kararlılıkla
birlikte verir.