Kova Sıralama Algoritması (Java, Python, C/C++ Code Örnekler)

Kova Sıralaması Nedir?

Kova Sıralama (Bucket Sort), genellikle kutu sıralama (bin sort) olarak da adlandırılır, sıralanmamış bir diziyi girdi olarak alan ve sıralanmış bir diziyi çıktı olarak üreten, karşılaştırmaya dayalı bir dağıtım sıralama yöntemidir. Bu teknik, elemanları birkaç kovaya dağıtır ve her kovayı ekleme sıralaması (insertion sort) gibi başka bir sıralama algoritması kullanarak ayrı ayrı sıralar. Daha sonra, tüm kovalar birleştirilerek nihai sıralanmış dizi oluşturulur.

Kova Sıralama algoritması genellikle şu durumlarda kullanılır:

1. Kayan nokta değerleri
2. Bilinen bir aralıkta düzgün dağılımlı

Kova Sıralama algoritmasının zaman karmaşıklığı, kullanılan kova sayısına ve girdi dağılımının tekdüzeliğine bağlıdır. Diğer sıralama algoritmaları ise, kabuk sıralaması, birleştirme sıralaması, yığın sıralaması ve hızlı sıralama En iyi durumda O(n*logn) zaman karmaşıklığına ulaşan Kova Sıralama algoritması, uygun koşullar altında doğrusal zaman karmaşıklığı O(n)'ye ulaşabilir.

Kova Sıralama algoritması, dağıtma-toplama yaklaşımını izler. Elemanlar ilgili kovalara dağıtılır, her kova içinde sıralanır ve son adımda sıralanmış bir dizi oluşturmak üzere toplanır. Bu dağıtma-toplama yaklaşımı aşağıdaki bölümde ele alınmaktadır.

Dağıtma-Toplama Yaklaşımı

Büyük ölçekli ve karmaşık problemlerin doğrudan çözümü bazen zor olabilir. Dağıtma-toplama yaklaşımı, tüm veri setini kümelere ayırarak bu tür sorunları ele alır. Her küme ayrı ayrı işlenir ve sonuçlar nihai cevabı üretmek için tekrar bir araya getirilir.

Kova Sıralama algoritması, dağıtma-toplama yöntemini şu şekilde uygular:

Kova Sıralaması Nasıl Çalışır?

Kova Sıralama algoritmasının temel çalışma prensibi şu şekildedir:

1. Boş kovalardan oluşan bir küme oluşturulur. Seçilen politikaya bağlı olarak kova sayısı değişebilir.
2. Giriş dizisinden her bir eleman, karşılık gelen kovaya yerleştirilir.
3. Her bir kova, ikincil bir sıralama algoritması kullanılarak ayrı ayrı sıralanır.
4. Sıralanmış gruplar birleştirilerek tek bir çıktı dizisi oluşturulur.

Sözde Code

Start
Create N empty buckets
For each array element:
    Calculate bucket index
    Put that element into the corresponding bucket
For each bucket:
    Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

Yöntem 1: Kayan Nokta için Kova Sıralama Algoritması Numbers

[0.0, 1.0] aralığındaki ondalık sayılar için Kova Sıralama algoritması:

) 1 Adım On (10) boş kova oluşturun. Birinci kova [0.0, 0.1) aralığındaki sayıları tutar. İkinci kova [0.1, 0.2) aralığındaki sayıları tutar ve bu şekilde devam eder.

) 2 Adım Her dizi öğesi için:

• a. Kova endeksini aşağıdaki formülü kullanarak hesaplayın:
  kova_indeksi = kova_sayısı * dizi_elemanı
• b. Öğeyi [bucket_index] kovasına ekle.

) 3 Adım Ekleme sıralamasını kullanarak her bir grubu ayrı ayrı sıralayın.

) 4 Adım Tüm grupları tek bir sıralı dizi halinde birleştirin.

Kova Sıralama (Bucket Sort) örneğini inceleyelim. Bu örnekte, aşağıdaki diziyi sıralayacağız:

) 1 Adım Öncelikle 10 boş kova oluşturuyoruz. Birinci kova [0.0, 0.1) aralığındaki sayıları, ikinci kova [0.1, 0.2) aralığındaki sayıları ve bu şekilde devam eden sayıları içeriyor.

) 2 Adım Dizideki her eleman için kova indeksini hesaplayın ve elemanı o kovaya yerleştirin.

Kova endeksi şu formül kullanılarak hesaplanır:
        kova_indeksi = kova_sayısı * dizi_elemanı

Kova Endeksi Hesaplaması:
a) 0.78
      kova_indeksi = kova_sayısı * dizi_elemanı
              = 10 * 0.78
              = 7.8
Dolayısıyla, 0.78 elemanı bucket[floor(7.8)] veya bucket[7]'de saklanır.

b) 0.17
      kova_indeksi = kova_sayısı * dizi_elemanı
              = 10 * 0.17
              = 1.7

Dizi elemanı 0.17, bucket[floor(1.7)] veya bucket[1]'de saklanır.

c) 0.39
      kova_indeksi = kova_sayısı * dizi_elemanı
              = 10 * 0.39
              = 3.9
0.39, bucket[floor(3.9)] veya bucket[3]'te saklanmaktadır.

Dizideki tüm elemanlar üzerinde yineleme yapıldıktan sonra, bölmeler şu şekilde görünür:

) 3 Adım Her bir kova daha sonra eklemeli sıralama yöntemi kullanılarak sıralanır. Sıralama işleminden sonra çıktı şu şekildedir:

) 4 Adım Son adımda, gruplar tek bir dizi halinde birleştirilir. Bu dizi, girdinin sıralanmış sonucudur.

Her bir kova, çıktı dizisine eklenir. Örneğin, ikinci kovanın elemanlarının birleştirilmesi şu şekildedir:

Son kova elemanlarının birleştirilmesi aşağıda gösterilmiştir:

Birleştirme işleminden sonra, elde edilen dizi istenen sıralı dizidir.

C/'de Kova Sıralama ProgramıC++

Giriş:

//Bucket Sort Program in C/C++
//For values without integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
  for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
    bucket[index].push_back(input[i]);
  }
  for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
  float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
  int array_size = sizeof(input)/sizeof(input[0]);

  bucketSort(input, array_size);
  cout <<"Sorted Output: 
";
  for (int i = 0; i< array_size; i++)
    cout<<input[i]<<" ";
  return 0;
}

Çıktı:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Kova Sıralama Programı Python

Giriş:

# Bucket Sort Program in Python
# For values without integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

Çıktı:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

Kova Sıralaması Java

Giriş:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List<Float>[] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList<>();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
                }
            }
        }
    }
    public static void main(String[] args) {
        float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

Çıktı:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Yöntem 2: Tamsayı Elemanları için Kova Sıralama Algoritması

[0.0, 1.0] aralığının ötesinde sayılar içeren girdiler için Kova Sıralama algoritması, önceki algoritmadan biraz farklıdır. algoritmaBu durum için gerekli adımlar şunlardır:

) 1 Adım Dizideki en büyük ve en küçük elemanları bulun.

) 2 Adım Kova sayısını (n) seçin ve kovaları başlangıçta boş olarak ayarlayın.

) 3 Adım Aşağıdaki formülü kullanarak her bir paketin aralığını veya aralığını hesaplayın:
        span = (maximum - minimum) / n

) 4 Adım Her dizi öğesi için:

• 1. Kova indeksini hesaplayın:
          bucket_index = (element - minimum) / span
• 2. Öğeyi [bucket_index] kovasına ekleyin.

) 5 Adım Ekleme sıralamasını kullanarak her bir grubu sıralayın.

) 6 Adım Tüm kovaları tek bir dizide birleştirin.

Kova Sıralama algoritmasının bir örneğini inceleyelim. Bu örnekte, aşağıdaki diziyi sıralayacağız:

) 1 Adım İlk adımda, verilen dizinin en büyük ve en küçük elemanlarını buluyoruz. Bu örnekte, en büyük eleman 24, en küçük eleman ise 1'dir.

) 2 Adım Ardından, boş kova sayısını, n'yi seçiyoruz. Bu örnekte, 5 kova kullanıyoruz ve bunları başlangıçta boş olarak belirliyoruz.

) 3 Adım Her bir kovanın açıklığı şu formül kullanılarak hesaplanır:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Dolayısıyla, birinci kova [0, 5) aralığındaki sayıları, ikinci kova [5, 10) aralığındaki sayıları ve bu şekilde devam eder.

) 4 Adım Her dizi elemanı için kova indeksini hesaplayın ve elemanı o kovaya yerleştirin. Kova indeksi şu formülle hesaplanır:
        bucket_index = (element - minimum) / span

Kova Endeksi Hesaplaması:

a) 11
kova_indeksi = (eleman – minimum) / aralık
        = (11 – 1) / 4
        = 2

Böylece, 11. eleman kova[2]'de saklanır.

b) 9
kova_indeksi = (eleman – minimum) / aralık
        = (9 – 1) / 4
        = 2

Not: 9, bucket[1] için bir sınır elemanı olduğundan, önceki elemanla aynı kovaya yerleştirilmek yerine bucket[1]'e eklenir.

Her bir eleman için işlemler gerçekleştirildikten sonra, gruplar aşağıdaki gibi görünür:

) 5 Adım Şimdi, her bir kova eklemeli sıralama yöntemi kullanılarak sıralanıyor. Sıralamadan sonraki kovalar:

) 6 Adım Son adımda, kovalar tek bir dizi halinde birleştirilir. dizi Bu, girdinin sıralanmış sonucudur.

C/'de Kova Sıralama ProgramıC++

Giriş:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>> output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     - int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1].push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double> input ={11,9,21,8,17,19,13,1,24,12};
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<"Sorted Output:";
  for (int i=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

Çıktı:

Sorted Output:1 8 9 11 12 13 17 19 21 24

Kova Sıralama Programı Python

Giriş:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:
", input)

Çıktı:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

Kova Sıralaması Java

Giriş:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List<List<Double>> output = new ArrayList<>();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList<>());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
            }
        }
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double> input = new ArrayList<>();
        input.add(11.0);
        input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
            System.out.print(value + " ");
        }
    }
}

Çıktı:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

Kova Sıralama Yönteminin Artıları ve Eksileri

Kova Sıralama Karmaşıklık Analizi

Kova Sıralama Süresi Karmaşıklığı

• En İyi Durum Karmaşıklığı: Eğer dizinin tüm elemanları eşit olarak dağıtılmış ve her bir bölme içinde önceden sıralanmışsa, elemanları ilgili bölmelere dağıtmak O(n) zaman alır. Ardından her bir bölmeyi sıralamak için ekleme türü Maliyetler O(k)'dir. Dolayısıyla genel karmaşıklık O(n+k)'dir.
• Ortalama Vaka Karmaşıklığı: Ortalama durumlar için, girdilerin düzgün dağılımlı olduğunu varsayıyoruz. Bu nedenle Kova Sıralama algoritması O(n+k) doğrusal zaman karmaşıklığına ulaşır. Burada, elemanları dağıtmak için O(n) zaman ve eklemeli sıralama kullanılarak sıralamak için O(k) zaman gereklidir.
• En Kötü Durum Karmaşıklığı: En kötü durumda, elemanlar eşit olarak dağılmaz ve bir veya iki grupta yoğunlaşır. Bu durumda, Kova Sıralama algoritması, aşağıdakine benzer bir davranış sergiler: kabarcık sıralama algoritmasıDolayısıyla, en kötü durumda, Kova Sıralama algoritmasının zaman karmaşıklığı O(n²)'dir.

Kova Sıralamasının Uzay Karmaşıklığı

Kova Sıralama algoritmasının alan karmaşıklığı O(n*k)'dir. Burada n, eleman sayısı ve k, sıralama sırasında bu elemanları tutmak için gereken kova sayısıdır.

SSS