Алгоритм сортування сегментів (Java, Python, C/C++ Code Приклади)

Що таке Bucket Sort?

Кошикове сортування, яке часто називають біновим сортуванням, — це метод сортування на основі розподілу, який приймає несортований масив на вхідні дані та створює відсортований масив на виході. Цей метод розподіляє елементи по кількох кошиках та сортує кожне кошичко окремо за допомогою іншого алгоритму сортування, такого як сортування вставками. Потім усі кошики об'єднуються разом, утворюючи остаточний відсортований масив.

Сортування за типом зазвичай використовується, коли елементи є:

1. Значення з плаваючою комою
2. Рівномірно розподілений у відомому діапазоні

Часова складність сортування за категоріями залежить від кількості використаних категорій та рівномірності розподілу вхідних даних. У той час як інші алгоритми сортування, такі як сортування оболонки, сортування злиттям, сортування в купі та швидкий досягти часової складності в найкращому випадку O(n*logn), алгоритм сортування Bucket Sort може досягти лінійної часової складності O(n) за сприятливих умов.

Сортування за методом розсіювання та збирання (Bucket Sort) дотримується методу розсіювання та збирання. Елементи розсіюються у відповідні сегменти, сортуються всередині кожного сегмента та збираються для формування відсортованого масиву на завершальному етапі. Цей підхід розсіювання та збирання обговорюється в наступному розділі.

Підхід розсіювання та збору

Масштабні, складні проблеми інколи може бути важко вирішити безпосередньо. Підхід розсіювання та збору вирішує такі проблеми, розділяючи весь набір даних на кластери. Кожен кластер обробляється окремо, а результати об'єднуються для отримання остаточної відповіді.

Ось як алгоритм сортування Bucket Sort реалізує метод розсіювання-збирання:

Як працює ковшове сортування

Основний принцип роботи сортування Bucket Sort полягає в наступному:

1. Створюється набір порожніх контейнерів. Кількість контейнерів може змінюватися залежно від обраної політики.
2. З вхідного масиву кожен елемент поміщається у відповідне відро.
3. Кожне відро сортується окремо за допомогою алгоритму вторинного сортування.
4. Відсортовані сегменти об'єднуються для створення одного вихідного масиву.

Псевдо 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

Спосіб 1: Алгоритм ковшового сортування для числа з плаваючою комою Numbers

Алгоритм сортування за допомогою Bucket Sort для чисел з плаваючою комою в діапазоні [0.0, 1.0]:

Крок 1) Створіть десять (10) порожніх сегментів. Перший сегмент містить числа в діапазоні [0.0, 0.1]. Другий сегмент містить [0.1, 0.2] тощо.

Крок 2) Для кожного елемента масиву:

• a. Розрахуйте індекс ковша за формулою:
  індекс_бакета = кількість_бакетів * елемент_масиву
• b. Вставте елемент у bucket[bucket_index]

Крок 3) Сортуйте кожне відро окремо за допомогою сортування вставкою.

Крок 4) Об'єднайте всі відра в один відсортований масив.

Давайте розглянемо приклад сортування за допомогою Bucket Sort. У цьому прикладі ми відсортуємо наступний масив:

Крок 1) Спочатку ми створюємо 10 порожніх сховищ. Перше сховище містить числа в діапазоні [0.0, 0.1]. Друге сховище містить [0.1, 0.2) тощо.

Крок 2) Для кожного елемента масиву обчисліть індекс корзини та помістіть елемент у цю корзину.

Індекс ковша розраховується за формулою:
        індекс_бакета = кількість_бакетів * елемент_масиву

Розрахунок індексу сегмента:
а) 0.78
      індекс_бакета = кількість_бакетів * елемент_масиву
              = 10 0.78 * XNUMX
              = 7.8
Отже, елемент 0.78 зберігається в bucket[floor(7.8)] або bucket[7].

b) 0.17
      індекс_бакета = кількість_бакетів * елемент_масиву
              = 10 0.17 * XNUMX
              = 1.7

Елемент масиву 0.17 зберігається в bucket[floor(1.7)] або bucket[1].

с) 0.39
      індекс_бакета = кількість_бакетів * елемент_масиву
              = 10 0.39 * XNUMX
              = 3.9
0.39 зберігається у bucket[floor(3.9)] або bucket[3].

Після перебору всіх елементів масиву, сегменти виглядають так:

Крок 3) Потім кожен сегмент сортується за допомогою сортування вставками. Після операції сортування результат має вигляд:

Крок 4) На останньому кроці сегменти об'єднуються в один масив. Цей масив є відсортованим результатом вхідних даних.

Кожне відро об'єднується з вихідним масивом. Наприклад, об'єднання елементів другого відра:

Об'єднання останніх елементів корзини показано нижче:

Після об'єднання результуючий масив є бажаним відсортованим масивом.

Програма сортування сегментів на C/C++

Вхідний сигнал:

//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;
}

вихід:

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

Bucket Sort Program in Python

Вхідний сигнал:

# 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))

вихід:

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[bucket_index]

Крок 5) Відсортуйте кожне відро за допомогою сортування вставкою.

Крок 6) Об’єднайте всі сегменти в один масив.

Розглянемо приклад цього алгоритму сортування за допомогою Bucket Sort. У цьому прикладі ми відсортуємо наступний масив:

Крок 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

Розрахунок індексу сегмента:

а) 11
bucket_index = (елемент – мінімум) / span
        = (11 – 1) / 4
        = 2

Таким чином, елемент 11 зберігається в контейнері[2].

b) 9
bucket_index = (елемент – мінімум) / span
        = (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=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

вихід:

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

Bucket Sort Program in 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:
", 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).
• Середня складність справи: Для середніх випадків ми припускаємо, що вхідні дані рівномірно розподілені. Таким чином, алгоритм сортування Bucket Sort досягає лінійної часової складності O(n+k). Тут для розсіювання елементів потрібно O(n), а для їх сортування за допомогою сортування вставками потрібно O(k).
• Найгірша складність: У найгіршому випадку елементи розподілені нерівномірно та зосереджені в одному або двох відрах. У такому випадку сортування за відра деградує до поведінки, подібної до алгоритм сортування бульбашкамиОтже, у найгіршому випадку часова складність сортування Bucket Sort становить O(n²).

Просторова складність ковшового сортування

Просторова складність сортування за допомогою Bucket Sort становить O(n*k). Тут n – це кількість елементів, а k – кількість відер, необхідних для їх зберігання під час сортування.

Поширені запитання