Kovalı Sıralama

Sıralama O(n + k) O(n + k)

Değerleri birkaç aralık kovasına dağıtır, her kovayı sıralar, sonra birleştirir — veri düzgün yayıldığında hızlıdır.

Boşta

8 eleman üzerinde Bucket Sort başlıyor (5 kova).

DeğişmezHer kova yalnızca kendi aralığından değer tutar, bu yüzden sıralı kovaları birleştirmek sıralı dizi verir.

1/31

karşılaştırma0hareket0sondaj0max0size0b0i0

karşılaştırtakaskaydırseçsıralı

bucket-sort.c

#define BUCKETS 5
 
void bucketSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
 
    int bucket[BUCKETS][100], count[BUCKETS] = {0};
    int size = max / BUCKETS + 1;
 
    for (int i = 0; i < n; i++) {
        int b = arr[i] / size;
        bucket[b][count[b]++] = arr[i];
    }
 
    for (int b = 0; b < BUCKETS; b++)
        insertionSort(bucket[b], count[b]);
 
    int idx = 0;
    for (int b = 0; b < BUCKETS; b++)
        for (int j = 0; j < count[b]; j++)
            arr[idx++] = bucket[b][j];
}

Kovalı Sıralama nasıl çalışır?

Değer aralığını birkaç kovaya böl, elemanları kovalara dağıt, her küçük kovayı sırala (eklemeli), sonra kovaları sırayla birleştir.

En iyi durum

Düzgün yayılmış veri — kovalar küçük kalır: yaklaşık O(n + k).

En kötü durum

Tüm değerler tek kovaya düşer — o kovanın sıralamasına döner: O(n²).

Ne zaman kullanılır?

Aralığa düzgün yayıldığı bilinen veriler (ör. [0,1) aralığında düzgün ondalıklar).