«Bucket Sort в Java» - Spring на русском

«1. Введение

В этой статье мы углубимся в алгоритм групповой сортировки. Мы начнем с небольшой теории, прежде чем работать над реализацией Java наряду с модульным тестированием нашего решения. Наконец, мы рассмотрим временную сложность сортировки ведра.

2. Теория сортировки сегментами

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

Давайте кратко рассмотрим шаги, необходимые для выполнения сортировки сегментов:

Set up an array of our initially empty buckets
Distribute our elements into their appropriate buckets
Sort each bucket
Concatenate the sorted buckets together to recreate the full list

3. Реализация Java

Хотя этот алгоритм не зависит от языка, мы будем реализовывать сортировку на Java. Давайте шаг за шагом пройдемся по приведенному выше списку и напишем код для сортировки списка целых чисел.

3.1. Настройка корзины

Во-первых, нам нужно определить алгоритм хэширования, чтобы решить, какие из наших элементов будут помещены в какую корзину:

private int hash(int i, int max, int numberOfBuckets) {
    return (int) ((double) i / max * (numberOfBuckets - 1));
}

Определив наш метод хеширования, мы теперь можем указать количество ячеек как квадратный корень. размера входного списка:

final int numberOfBuckets = (int) Math.sqrt(initialList.size());
List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);
for(int i = 0; i < numberOfBuckets; i++) {
    buckets.add(new ArrayList<>());
}

Наконец, нам нужен краткий метод для определения максимального целого числа в нашем входном списке:

private int findMax(List<Integer> input) {
    int m = Integer.MIN_VALUE;
    for (int i : input) {
        m = Math.max(i, m);
    }
    return m;
}

3.2. Распределение элементов

Теперь, когда мы определили наши корзины, мы можем распределить каждый элемент нашего входного списка в соответствующие корзины, используя метод хеширования:

int max = findMax(initialList);

for (int i : initialList) {
    buckets.get(hash(i, max, numberOfBuckets)).add(i);
}

3.3. Сортировка отдельных корзин

Когда наши корзины определены и заполнены целыми числами, давайте воспользуемся компаратором для их сортировки:

Comparator<Integer> comparator = Comparator.naturalOrder();

for(List<Integer> bucket  : buckets){
    bucket.sort(comparator);
}

3.4. Объединение наших корзин

Наконец, нам нужно объединить наши корзины, чтобы воссоздать единый список. Так как наши корзины отсортированы, нам нужно пройтись по каждой корзине только один раз и добавить элементы в основной список:

List<Integer> sortedArray = new LinkedList<>();

for(List<Integer> bucket : buckets) {
    sortedArray.addAll(bucket);
} 

return sortedArray;

4. Тестирование нашего кода

Когда наша реализация завершена, давайте напишем быстрый модульный тест для убедитесь, что он работает должным образом:

BucketSorter sorter = new IntegerBucketSorter();

List<Integer> unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15);
List<Integer> expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602);

List<Integer> sorted = sorter.sort(unsorted);

assertEquals(expected, sorted);

5. Временная сложность

Далее, давайте кратко рассмотрим временную сложность выполнения сортировки ведром.

5.1. Сценарий наихудшего случая

В нашем наихудшем сценарии мы нашли бы все наши элементы в одном и том же сегменте и в обратном порядке. Когда происходит этот случай, мы сокращаем нашу сортировку ведра до простой сортировки, в которой каждый элемент сравнивается с каждым другим элементом, что дает временную сложность O (n²).

5.2. Сценарий среднего случая

В нашем среднем случае мы обнаруживаем, что элементы относительно равномерно распределены между нашими входными сегментами. Поскольку для каждого из наших шагов требуется только одна итерация по нашим входным сегментам, мы обнаруживаем, что наша сортировка по сегментам завершается за время O(n).

6. Заключение

В этой статье мы увидели, как реализовать сортировку сегментов в Java. Мы также рассмотрели временную сложность алгоритма сортировки ведра.

Как всегда, код, показанный в этой статье, доступен на GitHub.

«Bucket Sort в Java»