Kova Sıralama Algoritması (Java, Python, C/C++ Kod Örnekleri)
Sarah Chen
Kova Sıralaması Nedir?
Genellikle bin sort olarak adlandırılan kova sıralaması, sıralanmamış bir diziyi girdi olarak kabul eden ve sonuç olarak sıralanmış bir dizi üreten bir karşılaştırmalı sıralama yöntemidir. Bu yöntem, öğeleri birkaç bölüme dağıtarak ve bu bölümlerin her birini ekleme sıralaması gibi herhangi bir sıralama algoritmasıyla ayrı ayrı sıralayarak çalışır. Daha sonra tüm kovalar sıralanmış bir dizi oluşturacak şekilde birleştirilir.
Kova sıralaması genellikle öğeler aşağıdaki durumlarda kullanılır:
- Kayan nokta değerleri
- Belirli bir aralıkta eşit olarak dağıtılmış
Kova sıralamasının zaman karmaşıklığı kullanılan kova sayısına ve giriş dağılımının tekdüzeliğine bağlıdır. Farklı sıralama algoritmaları gibi kabuk sıralaması, birleştirme sıralaması, yığın sıralaması ve hızlı sıralama En iyi durum zaman karmaşıklığı olan O(n*logn) elde edilebilirken, kova sıralama algoritması aynı zamanda doğrusal zaman karmaşıklığı olan O(n)'de de elde edilebilir.
Kova sıralaması, dağıtma-toplama yaklaşımını takip eder. Bu yaklaşımı uygulayarak, elemanlar karşılık gelen kovalara dağıtılır, kovalarda sıralanır ve son adım olarak 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ğıt-Topla-Yaklaşımı
Büyük ölçekli, karmaşık problemler bazen çözülmesi zor olabilir. Dağılım-toplama yaklaşımı, tüm veri setini kümelere bölerek bu tür problemleri çözmeye çalışır. Daha sonra her küme ayrı ayrı ele alınır ve nihai cevaba ulaşmak için her şey tekrar bir araya getirilir.
Kova sıralama algoritması dağılım-toplama yöntemini şu şekilde uygular:
Kova Sıralaması Nasıl Çalışır?
Kova sıralamasının temel çalışma prensibi şu şekildedir:
- Bir dizi boş kova oluşturulur. Farklı politikalara bağlı olarak paket sayısı farklılık gösterebilir.
- Giriş dizisinden her öğeyi karşılık gelen klasöre yerleştirin.
- Bu kovaları tek tek sıralayın.
- Tek bir çıktı dizisi oluşturmak için sıralanan paketleri birleştirin.
Ayrıntılı çalışma adımları aşağıdaki bölümlerde yer almaktadır.
Sözde Kod
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 ile 1.0 aralığındaki kayan nokta sayıları için kova sıralama algoritması:
) 1 Adım İlk bölümün [10, 0.0] aralığında sayılar içerecek şekilde on(0.1) boş bölüm oluşturun. Daha sonra ikinci kova [0.1, 0.2) dahilinde olacaktır ve bu böyle devam edecektir.
) 2 Adım Her dizi öğesi için:
-
A. Aşağıdaki formülü kullanarak kova endeksini hesaplayın:
paket dizini= no_of_buckets *array_element
-
B. Öğeyi pakete[bucket_index] ekleyin
) 3 Adım Ekleme sıralamasını kullanarak her bir grubu ayrı ayrı sıralayın.
) 4 Adım Tüm paketleri tek bir dizide birleştirin.
Bir kova sıralama örneğine bakalım. Bu örnek için, kova sıralama algoritmasını kullanarak aşağıdaki diziyi sıralayacağız:
) 1 Adım Öncelikle 10 adet boş kova oluşturacağız. İlk grup [0.0, 0.1) arasındaki sayıları içerecektir. Daha sonra ikinci kova [0.1, 0.2) arasındaki sayıları içerecektir.
) 2 Adım Her dizi elemanı için kova indeksini hesaplayacağız ve elemanı o kovaya yerleştireceğiz.
Kova endeksi aşağıdaki formül kullanılarak hesaplanabilir:
Bucket_index= no_of_buckets*array_element
Kova Endeksi Hesaplaması:
a) 0.78
Bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Dolayısıyla 0.78 elemanı kova[zemin(7.8)] veya kova[7] üzerinde depolanacaktır.
b) 0.17
Bucket_index = no_of_buckets * dizi öğesi
= 10 * 0.17
= 1.7
0.17 dizi öğesi kova[kat(1.7)] veya kova[1]'de depolanacaktır.
c) 0.39
Bucket_index = no_of_buckets * dizi öğesi
= 10 * 0.39
= 3.9
0.39 kova[zemin(3.9)] veya kova[3] üzerinde depolanacaktır.
Tüm dizi öğeleri üzerinde yineleme yaptıktan sonra, kovalar aşağıdaki gibi olacaktır:
) 3 Adım Daha sonra her bir paket, ekleme sıralaması kullanılarak sıralanacaktır. Sıralama işleminden sonra çıktı şu şekilde olacaktır:
) 4 Adım Son adımda kovalar tek bir dizide birleştirilecektir. Bu dizi girdinin sıralanmış sonucu olacaktır.
Her paket çıkış dizisine birleştirilecektir. Örneğin ikinci kova elemanlarının birleştirilmesi:
Son kova elemanlarının birleşimi şu şekilde olacaktır:
Birleştirmeden sonra ortaya çıkan dizi, istenen sıralanmış dizi olacaktır.
C/'de Kova Sıralama ProgramıC++
Giriş:
//Bucket Sort Program in C/C++
//For not having 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: \n";
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 not having 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 giriş için paket sıralama algoritması öncekinden biraz farklıdır algoritma. Bu durum için gerekli adımlar aşağıdaki gibidir:
) 1 Adım Maksimum ve minimum elemanları bulun.
) 2 Adım Demet sayısını (n) seçin ve bu demetleri boş olarak başlatı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 endeksini hesaplayın:
bucket_index = (element - minimum)/span-
2. Elemanı kovaya[bucket_index] yerleştirin
) 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.
Bu kova sıralama algoritmasının bir örneğine bakalım. Bu örnek için, kova sıralama algoritmasını kullanarak aşağıdaki diziyi sıralayacağız-
) 1 Adım İlk adımda verilen dizinin maksimum ve minimum elemanlarının bulunması gerekmektedir. Bu örnekte maksimum 24 ve minimum 1'dir.
) 2 Adım Şimdi bir dizi boş kova seçmeliyiz, n. Bu örnekte 5 kova alacağız. Daha sonra bunları boş olarak başlatacağız.
) 3 Adım Her bir kovanın genişliği aşağıdaki formülle hesaplanmalıdır:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Dolayısıyla ilk kova [0, 5) aralığındaki sayıları içerecektir. İkinci grup [5, 10) vb. içindeki sayıları içerecektir.
) 4 Adım Her dizi elemanı için kova indeksini hesaplayacağız ve elemanı o kovaya yerleştireceğiz. Kova endeksi aşağıdaki formül kullanılarak hesaplanabilir:
bucket_index = (element - minimum)/span
Kova Endeksi Hesaplaması:
-
a) 11bucket_index = (öğe – minimum)/aralık
=(11-1)/4
=2
Böylece 11 numaralı eleman kova[2]'de depolanacaktır.
-
b) 9
Bucket_index = (öğe – minimum)/aralık
=(9-1)/4
=2
Not: 9, kova[1] için bir sınır elemanı olduğundan, önceki elemanın aynı kovasına eklemek yerine kovaya[1] eklenmesi gerekir.
Her bir eleman için işlemler yapıldıktan sonra kovalar aşağıdaki gibi olacaktır:
) 5 Adım Artık her paket ekleme sıralaması kullanılarak sıralanacak. Ayırdıktan sonra kovalar...
) 6 Adım Son adımda kovalar tek bir dizide birleştirilecektir. O dizi girdinin sıralanmış sonucu olacaktır.
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; 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:\n", 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
Artılar ve eksiler
| Artılar | Eksiler |
|---|---|
| Daha hızlı hesaplama gerçekleştirin | Diğer algoritmalara göre daha fazla yer tüketir |
| Harici bir sıralama yöntemi olarak kullanılabilir | Veriler eşit şekilde dağıtılmadığında kötü performans gösterir |
| Kovalar bağımsız olarak işlenebilir |
Kova Sıralama Karmaşıklık Analizi
Kova Sıralamasının Zaman Karmaşıklığı
- En İyi Durum Karmaşıklığı:Dizinin tüm elemanları önceden eşit şekilde dağıtılmış ve sıralanmışsa, elemanları karşılık gelen bölmelere dağıtmak O(n) süresine ihtiyaç duyacaktır. Daha sonra her bir kovayı kullanarak sıralama ekleme türü maliyeti O(k) olurdu. Dolayısıyla genel karmaşıklık O(n+k) olurdu.
- Ortalama Vaka Karmaşıklığı:Ortalama durumlar için girdilerin düzgün dağıtıldığını 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 bu elemanları ekleme sıralaması kullanarak sıralamak için O(k) zaman gerekir.
- En Kötü Durum Karmaşıklığı:En kötü durumda, öğeler bir veya iki belirli kova üzerinde eşit şekilde dağıtılmayacak ve yoğunlaşmayacaktır. Bu durumda, kova sıralaması şu şekilde çalışacaktır: kabarcık sıralama algoritması. Bu nedenle, en kötü durumda, bir kova sıralamasının zaman karmaşıklığı O(n^2) olacaktır.
Kova Sıralamasının Uzay Karmaşıklığı
Kova sıralamasının uzay karmaşıklığı O(n*k)'dır. Burada n eleman sayısı ve k gerekli kova sayısıdır.
