Bucket Sort в Java

1. Введение

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

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

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

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

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

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 .