Алгоритм сортировки сегментов (примеры кода на Java, Python, C/C++)

Что такое групповая сортировка?

Сортировка сегментами, часто называемая сортировкой ячеек, представляет собой метод сортировки сравнением, который принимает несортированный массив в качестве входных данных и в результате создает отсортированный массив. Этот метод работает путем распределения элементов по нескольким сегментам и индивидуальной сортировки каждого из этих сегментов с помощью любого алгоритма сортировки, например сортировки вставками. Затем все сегменты объединяются в отсортированный массив.

Сортировка сегментами обычно используется, когда элементы:

  1. Значения с плавающей запятой
  2. Равномерно распределены по диапазону

Время сортировки ведром complexэффективность зависит от количества используемых ковшей и равномерности распределения входных данных. Хотя различные алгоритмы сортировки, такие как сортировка по скорлупе, сортировка слиянием, пирамидальная сортировка и быстрая сортировка может достичь наилучшего времени complexЕсли значение O(n*logn), то алгоритм сортировки сегментами может достичь того же за линейное время com.plexity или O(n).

Сортировка сегментами соответствует подходу «разброс-сбор». Применяя этот подход, элементы распределяются по соответствующим сегментам, сортируются в сегментах и ​​на последнем этапе собираются для формирования отсортированного массива. Этот подход рассеяния и сбора обсуждается ниже.wing .

Метод рассеяния и сбора

Крупномасштабный, комplex проблемы иногда могут быть трудными для решения. Подход «разброс-сбор» пытается решить такие проблемы путем разделения всего набора данных на кластеры. Затем к каждому кластеру обращаются отдельно и собирают все вместе, чтобы получить окончательный ответ.

Вот как алгоритм сортировки сегментов реализует метод разброса и сбора:

Метод рассеяния и сбора

Как работает сегментная сортировка

Основной принцип работы сортировки по сегментам заключается в следующем:

  1. Создаётся набор пустых корзин. В зависимости от разных политик количество сегментов может различаться.
  2. Из входного массива поместите каждый элемент в соответствующее ведро.
  3. Отсортируйте эти ведра по отдельности.
  4. Объедините отсортированные сегменты, чтобы создать единый выходной массив.

Подробные этапы работы приведены ниже.wing раздел.

Псевдокод

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. Алгоритм групповой сортировки для чисел с плавающей запятой

Алгоритм сортировки ячеек для чисел с плавающей запятой в диапазоне от 0.0 до 1.0:

Шаг 1) Создайте десять (10) пустых сегментов так, чтобы первый блок содержал числа в диапазоне [0.0, 0.1). Тогда второй блок будет содержать значения в пределах [0.1, 0.2) и так далее.

Шаг 2) Для каждого элемента массива:

      а. Рассчитайте индекс сегмента по формуле:
      индекс сегмента = no_of_buckets *array_element
      б. Вставьте элемент в корзину[bucket_index]

Шаг 3) Отсортируйте каждую корзину по отдельности, используя сортировку вставками.

Шаг 4) Объедините все сегменты в один массив.

Давайте посмотрим пример сортировки по сегментам. В этом примере мы отсортируем следующееwing массив с использованием алгоритма сортировки сегментов -

Алгоритм сегментной сортировки для чисел с плавающей запятой

Шаг 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].

Алгоритм сегментной сортировки для чисел с плавающей запятой

После перебора всех элементов массива сегменты будут такими же:wing:

Алгоритм сегментной сортировки для чисел с плавающей запятой

Шаг 3) Затем каждый блок будет отсортирован с использованием сортировки вставками. После операции сортировки результат будет таким:

Алгоритм сегментной сортировки для чисел с плавающей запятой

Шаг 4) На последнем этапе сегменты будут объединены в один массив. Этот массив будет отсортированным результатом ввода.

Каждый сегмент будет объединен с выходным массивом. Например — объединение элементов второго ведра:

Алгоритм сегментной сортировки для чисел с плавающей запятой

Объединение последних элементов сегмента будет следующим:wing:

Алгоритм сегментной сортировки для чисел с плавающей запятой

После объединения результирующий массив будет желаемым отсортированным массивом.

Алгоритм сегментной сортировки для чисел с плавающей запятой

Программа сортировки сегментов на 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) Объедините все сегменты в один массив.

Давайте посмотрим пример этого алгоритма сортировки по сегментам. В этом примере мы отсортируем следующееwing массив с использованием алгоритма сортировки сегментов -

Алгоритм сортировки сегментов для целочисленных элементов

Шаг 1) На первом этапе необходимо найти максимальный и минимальный элементы данного массива. В этом примере максимум — 24, минимум — 1.

Шаг 2) Теперь нам нужно выбрать количество пустых ведер n. В этом примере мы возьмем 5 ведер. Затем мы инициализируем их как пустые.

Шаг 3) Пролет каждого ковша необходимо рассчитать по следующему принципу:wing формула:
               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

Плюсы и минусы

Плюсы Минусы
Выполняйте более быстрые вычисления Занимает больше места по сравнению с другими алгоритмами
Его можно использовать как внешний метод сортировки. Плохо работает, когда данные распределены неравномерно.
Ведра можно обрабатывать самостоятельно

Ведровая сортировкаplexАнализ города

Время Com сегментной сортировкиplexность

  • Лучший случайplexность:Если все элементы массива равномерно распределены и заранее отсортированы, для распределения элементов по соответствующим сегментам потребуется время O(n). Затем сортируем каждое ведро, используя сортировка вставок будет стоить O(k). Таким образом, общая комplexэффективность будет равна O(n+k).
  • Средний случай, ком.plexность:В средних случаях мы предполагаем, что входные данные распределены равномерно. Таким образом, алгоритм сортировки сегментов обеспечивает линейное время com.plexность O(n+k). Здесь время O(n) требуется для разброса элементов, а время O(k) требуется для сортировки этих элементов с использованием сортировки вставками.
  • Наихудший случайplexность:В худшем случае элементы не будут равномерно распределены и сконцентрированы в одном или двух конкретных сегментах. В этом случае сегментная сортировка будет работать как Алгоритм пузырьковой сортировки. Следовательно, в худшем случае время complexСтепень сортировки корзины будет равна O(n^2).

Космическая связьplexСущность сегментной сортировки

Космос сортировки ведромplexity равен O(n*k). Здесь n — количество элементов, а k — необходимое количество сегментов.