Алгоритм сортировки сегментов (Java, Python, С /C++ Примеры кода)
Сара Чен
Что такое групповая сортировка?
Сортировка сегментами, часто называемая сортировкой ячеек, представляет собой метод сортировки сравнением, который принимает несортированный массив в качестве входных данных и в результате создает отсортированный массив. Этот метод работает путем распределения элементов по нескольким сегментам и индивидуальной сортировки каждого из этих сегментов с помощью любого алгоритма сортировки, например сортировки вставками. Затем все сегменты объединяются в отсортированный массив.
Сортировка сегментами обычно используется, когда элементы:
- Значения с плавающей запятой
- Равномерно распределены по диапазону
Временная сложность сортировки сегментов зависит от количества используемых сегментов и равномерности распределения входных данных. Хотя различные алгоритмы сортировки, такие как сортировка по скорлупе, сортировка слиянием, пирамидальная сортировка и быстрая сортировка может достичь наилучшей временной сложности O(n*logn), алгоритм сортировки сегментами может достичь того же при линейной временной сложности или O(n).
Сортировка сегментами соответствует подходу «разброс-сбор». Применяя этот подход, элементы распределяются по соответствующим сегментам, сортируются в сегментах и на последнем этапе собираются для формирования отсортированного массива. Этот подход рассеяния и сбора обсуждается в следующем разделе.
Метод рассеяния и сбора
Крупномасштабные и сложные проблемы иногда могут оказаться трудными для решения. Подход «разброс-сбор» пытается решить такие проблемы путем разделения всего набора данных на кластеры. Затем к каждому кластеру обращаются отдельно и собирают все вместе, чтобы получить окончательный ответ.
Вот как алгоритм сортировки сегментов реализует метод разброса и сбора:
Как работает сегментная сортировка
Основной принцип работы сортировки по сегментам заключается в следующем:
- Создаётся набор пустых корзин. В зависимости от разных политик количество сегментов может различаться.
- Из входного массива поместите каждый элемент в соответствующее ведро.
- Отсортируйте эти ведра по отдельности.
- Объедините отсортированные сегменты, чтобы создать единый выходной массив.
Подробные этапы работы представлены в следующих разделах.
Псевдокод
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 *array_element
-
б. Вставьте элемент в корзину[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)] или ведре[7].
б) 0.17
Bucket_index = no_of_buckets * элемент массива
= 10 * 0.17
= 1.7
Элемент массива 0.17 будет сохранен в ведре[floor(1.7)] или ведре[1].
в) 0.39
Bucket_index = no_of_buckets * элемент массива
= 10 * 0.39
= 3.9
0.39 будет храниться в ведре[floor(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
Расчет индекса ковша:
-
а) 11bucket_index = (элемент – минимум)/диапазон
=(11-1)/4
=2
Таким образом, элемент 11 будет сохранен в ведре[2].
-
б) 9
Bucket_index = (элемент – минимум)/диапазон
=(9-1)/4
=2
Примечание: Поскольку 9 является граничным элементом для сегмента [1], его необходимо добавить в сегмент [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
Плюсы и минусы
| Плюсы | Минусы |
|---|---|
| Выполняйте более быстрые вычисления | Занимает больше места по сравнению с другими алгоритмами |
| Его можно использовать как внешний метод сортировки. | Плохо работает, когда данные распределены неравномерно. |
| Ведра можно обрабатывать самостоятельно |
Анализ сложности сегментной сортировки
Временная сложность сегментной сортировки
- лучшая сложность дела:Если все элементы массива равномерно распределены и заранее отсортированы, для распределения элементов по соответствующим сегментам потребуется время O(n). Затем сортируем каждое ведро, используя сортировка вставок будет стоить O(k). Таким образом, общая сложность будет равна O(n+k).
- Средняя сложность дела:В средних случаях мы предполагаем, что входные данные распределены равномерно. Таким образом, алгоритм сортировки сегментов достигает линейной временной сложности O(n+k). Здесь время O(n) требуется для разброса элементов, а время O(k) требуется для сортировки этих элементов с использованием сортировки вставками.
- Наихудшая сложность случая:В худшем случае элементы не будут равномерно распределены и сконцентрированы в одном или двух конкретных сегментах. В этом случае сегментная сортировка будет работать как Алгоритм пузырьковой сортировки. Следовательно, в худшем случае временная сложность сортировки сегментом будет равна O(n^2).
Пространственная сложность сортировки ведром
Пространственная сложность сортировки сегментов равна O(n*k). Здесь n — количество элементов, а k — необходимое количество сегментов.
