Алгоритъм за сортиране на кофа (Java, Python, C/C++ Примери за код)
Сара Чен
Какво е Bucket Sort?
Bucket сортиране, често наричано bin сортиране, е метод за сортиране за сравнение, който приема несортиран масив като вход и създава сортиран масив като резултат. Този метод работи, като разпределя елементите в няколко кофи и сортира всяка от тези кофи поотделно чрез произволен алгоритъм за сортиране, като сортиране чрез вмъкване. След това всички кофи се обединяват, за да образуват сортиран масив.
Кофичното сортиране обикновено се използва, когато елементите са-
- Стойности с плаваща запетая
- Равномерно разпределени в диапазон
Времевата сложност на сортирането на кофа зависи от броя на използваните кофи и равномерността на входното разпределение. Докато различни алгоритми за сортиране като напр сортиране на черупки, сортиране чрез сливане, групово сортиране и бърз сорт може да постигне най-добрата времева сложност на O(n*logn), алгоритъмът за сортиране на кофа може да постигне същото при линейна времева сложност или O(n).
Кофичното сортиране следва подхода на разпръснато събиране. Прилагайки този подход, елементите се разпръскват в съответните кофи, сортират се в кофите и се събират, за да образуват сортиран масив като последна стъпка. Този подход на разпръснато събиране се обсъжда в следващия раздел
Разпръскване-събиране-подход
Мащабните, сложни проблеми понякога могат да бъдат предизвикателство за разрешаване. Подходът на разпръснато събиране се опитва да реши такива проблеми чрез разделяне на целия набор от данни на клъстери. След това всеки клъстер се адресира отделно и всичко се събира обратно, за да се получи окончателният отговор.
Ето как алгоритъмът за сортиране на кофата прилага метода на събиране на разсейване:
Как работи Bucket Sort
Основният принцип на работа на сортирането на кофи е следният:
- Създава се набор от празни кофи. Въз основа на различни политики броят на кофите може да се различава.
- От входния масив поставете всеки елемент в съответната му кофа.
- Сортирайте тези кофи поотделно.
- Свържете сортираните кофи, за да създадете един изходен масив.
Подробните работни стъпки са предоставени в следващите раздели.
Псевдо код
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
Метод 1: Алгоритъм за сортиране на кофа за плаваща запетая Numbers
Алгоритъмът за сортиране на кофа за числа с плаваща запетая в диапазона от 0.0 до 1.0:
Стъпка 1) Създайте десет (10) празни кофи, така че първата кофа да съдържа числа в диапазона [0.0, 0.1). Тогава втората кофа ще съдържа в рамките на [0.1, 0.2) и т.н.
Стъпка 2) За всеки елемент от масива:
-
а. Изчислете индекса на кофата, като използвате формулата:
индекс на кофа= no_of_buckets *елемент_масив
-
b. Вмъкнете елемента в кофата [bucket_index]
Стъпка 3) Сортирайте всяка кофа поотделно, като използвате сортиране чрез вмъкване.
Стъпка 4) Свържете всички кофи в един масив.
Нека видим пример за сортиране на кофа. За този пример ще сортираме следния масив, като използваме алгоритъма за сортиране на кофа -
Стъпка 1) Първо ще създадем 10 празни кофи. Първата група ще съдържа числата между [0.0, 0.1). След това втората група ще съдържа числата между [0.1, 0.2) и т.н.
Стъпка 2) За всеки елемент от масива ще изчислим индекса на кофата и ще поставим елемента в тази кофа.
Индексът на кофата може да се изчисли по формулата:
bucket_index= no_of_buckets*array_element
Изчисляване на индекса на групата:
а) 0.78
bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Следователно елементът 0.78 ще бъде съхранен в кофата[floor(7.8)] или bucket[7].
б) 0.17
bucket_index = no_of_buckets * елемент от масива
= 10 * 0.17
= 1.7
Елементът на масива 0.17 ще се съхранява на bucket[floor(1.7)] или bucket[1].
в) 0.39
bucket_index = no_of_buckets * елемент от масива
= 10*0.39
= 3.9
0.39 ще се съхранява в кофа [под (3.9)] или кофа [3].
След повторение на всички елементи на масива кофите ще бъдат следните:
Стъпка 3) След това всяка кофа ще бъде сортирана чрез сортиране чрез вмъкване. След операцията по сортиране изходът ще бъде:
Стъпка 4) В последната стъпка кофите ще бъдат свързани в един масив. Този масив ще бъде сортираният резултат от входа.
Всяка кофа ще бъде свързана към изходния масив. Например - конкатенацията на вторите елементи на кофата:
Конкатенацията на последните елементи на кофата ще бъде следната:
След конкатенацията полученият масив ще бъде желаният сортиран масив.
Програма за сортиране на кофи в C/C++
Вход:
//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;
}
Изход:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Програма за сортиране на кофа в Python
Вход:
# 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))
Изход:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Кофа Сортиране в Java
Вход:
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]+" ");
}
}
}
Изход:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Метод 2: Алгоритъм за сортиране на кофа за цели числа
Алгоритъмът за сортиране на кофа за вход, който съдържа числа извън диапазона [0.0, 1.0], е малко по-различен от предишния алгоритъм. Необходимите стъпки за този случай са следните-
Стъпка 1) Намерете максималния и минималния елемент.
Стъпка 2) Изберете броя кофи, n, и инициализирайте тези кофи като празни.
Стъпка 3) Изчислете диапазона или обхвата на всяка кофа, като използвате формулата:
span = (maximum - minimum)/n
Стъпка 4) За всеки елемент от масива:
-
1. Изчислете индекса на кофата:
bucket_index = (element - minimum)/span-
2. Вмъкнете елемента в кофа [bucket_index]
Стъпка 5) Сортирайте всяка кофа чрез сортиране чрез вмъкване.
Стъпка 6) Свържете всички кофи в един масив.
Нека видим пример за този алгоритъм за сортиране на кофа. За този пример ще сортираме следния масив, като използваме алгоритъма за сортиране на кофа -
Стъпка 1) В първата стъпка трябва да се намерят максималния и минималния елемент на дадения масив. За този пример максимумът е 24, а минимумът е 1.
Стъпка 2) Сега трябва да изберем брой празни кофи, n. В този пример ще вземем 5 кофи. След това ще ги инициализираме като празни.
Стъпка 3) Обхватът на всяка кофа трябва да се изчисли по следната формула:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Следователно, първата група ще съдържа числата в диапазона [0, 5). Втората група ще съдържа числата в [5, 10) и т.н.
Стъпка 4) За всеки елемент от масива ще изчислим индекса на кофата и ще поставим елемента в тази кофа. Индексът на кофата може да се изчисли по формулата:
bucket_index = (element - minimum)/span
Изчисляване на индекса на групата:
-
a) 11bucket_index = (елемент – минимум)/обхват
=(11-1)/4
=2
По този начин елемент 11 ще бъде съхранен в кофа [2].
-
б) 9
bucket_index = (елемент – минимум)/обхват
=(9-1)/4
=2
Забележка: Тъй като 9 е граничен елемент за bucket[1], той трябва да бъде добавен в bucket[1], вместо да се добавя в същата кофа на предишния елемент.
След извършване на операциите за всеки елемент кофите ще бъдат както следва:
Стъпка 5) Сега всяка кофа ще бъде сортирана чрез сортиране чрез вмъкване. Кофите след сортиране-
Стъпка 6) В последната стъпка кофите ще бъдат свързани в един масив. това масив ще бъде сортираният резултат от въвеждането.
Програма за сортиране на кофи в C/C++
Вход:
#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;
}
Изход:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Програма за сортиране на кофа в Python
Вход:
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)
Изход:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Кофа Сортиране в Java
Вход:
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 + " ");
}
}
}
Изход:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Плюсове минуси
| Професионалисти | Против |
|---|---|
| Извършвайте по-бързи изчисления | Консумира повече място в сравнение с други алгоритми |
| Може да се използва като външен метод за сортиране | Работи лошо, когато данните не са равномерно разпределени |
| Кофите могат да се обработват независимо |
Анализ на сложността на сортиране на кофа
Времева сложност на Bucket Sort
- Сложност в най-добрия случай:Ако всички елементи на масива са равномерно разпределени и сортирани предварително, ще е необходимо O(n) време за разпръскване на елементите в съответните кофи. След това сортирайте всяка кофа с помощта на вмъкване сортиране би струвало O(k). Така общата сложност ще бъде O(n+k).
- Средна сложност на случая:За средни случаи приемаме, че входовете са равномерно разпределени. По този начин алгоритъмът за сортиране на кофа постига линейна времева сложност от O(n+k). Тук O(n) време е необходимо за разпръскване на елементите и O(k) време е необходимо за сортиране на тези елементи чрез сортиране чрез вмъкване.
- Сложност в най-лошия случай:В най-лошия случай елементите няма да бъдат равномерно разпределени и концентрирани в една или две конкретни кофи. В този случай bucket sort ще работи като a алгоритъм за сортиране на мехурчета. Следователно, в най-лошия случай, времевата сложност на сортиране в кофа ще бъде O(n^2).
Пространствена сложност на Bucket Sort
Пространствената сложност на кофата за сортиране е O(n*k). Тук n е броят на елементите, а k е броят на необходимите кофи.