Алгоритмы сортировки
Bucket Sort: визуализируйте, проектируйте и анализируйте.
Знать полный анализ алгоритма сортировки ведра.
Давайте поговорим об алгоритме Bucket Sort: его визуализации, дизайне и анализе.
Что такое Bucket sort?
Bucket Sort используется, когда входные числа равномерно распределены по диапазону. Следующая задача иллюстрирует использование алгоритма сортировки ведра.
Eg: Sort a large set of floating-point numbers that are in
the range from 0.0 to 1.0 and are uniformly distributed across the range.
Let’s say the numbers are {0.42,0.32,0.23,0.52,0.25,0.47,0.51}.
Как мы можем эффективно сортировать эти числа?
Мы можем использовать любой алгоритм сортировки на основе сравнения. Но нижняя граница для алгоритма сортировки на основе сравнения составляет Ω(n log n) (сортировка слиянием, сортировка кучей, быстрая сортировка и т. д.). Эти алгоритмы не могут работать лучше, чем Ω(n log n).
Мы можем использовать сортировку подсчетом для сортировки этих элементов за линейное время, но сортировку подсчетом здесь нельзя применить, поскольку мы используем ключи в качестве индекса при сортировке подсчетом, и в этом случае ключи представляют собой числа с плавающей запятой.
Поэтому мы будем использовать новый алгоритм сортировки, который называется сортировка по сегментам. Сортировка сегментами — это метод сортировки, при котором элементы сортируются путем разделения элементов на несколько групп, называемых сегментами. Элементы внутри каждого сегмента сортируются с использованием любого из подходящих алгоритмов сортировки или рекурсивного вызова одного и того же алгоритма.
Создается несколько ведер. Каждое ведро заполнено определенным набором элементов. Элементы внутри ведра сортируются по любому другому алгоритму. Наконец, элементы корзины собираются для получения отсортированного массива.
Давайте визуализируем алгоритм сортировки сегментов на примере:
- Учитывая массив и создание нового массива для хранения элементов данного массива.
2. Вставить в корзины элементы из заданного массива. Элементы вставляются в соответствии с диапазоном ведра.
Теперь пусть у нас есть сегменты от 0 до 1, от 1 до 2, от 2 до 3,…… (n-1) до n, где n — размер массива сегментов. В приведенном выше примере это 10.
Возьмем входной элемент 0,32. Он умножается на размер нового массива 0,32*10 = 3,2 =› и преобразуется в 3, поскольку индексы нового массива находятся в диапазоне только от 0–9, и эти индексы целые числа. Наконец, .32 вставляется в корзину 3.
Точно так же .25 также вставляется в тот же сегмент.
После вставки всех элементов в соответствующие ведра.
3. Теперь элементы каждой корзины сортируются по любому из алгоритмов стабильной сортировки. Мы использовали быструю сортировку, встроенную функцию в java.
4. Элементы из каждой корзины собираются и помещаются в исходный массив путем перебора корзин.
Теперь давайте разработаем алгоритм сортировки ведра:
bucketSort(arr[], n)
1. Create 'n' empty buckets using some data structure.
2. For each array element arr[i].
2.1 Insert arr[i] into bucket[n*array[i]]
3. Sort individual buckets using insertion sort.
4. Now concatenate all the sorted buckets and create single array.
Java-программа для сортировки ведра:
ВЫХОД:
Sorted Array : 0.32 0.33 0.37 0.42 0.47 0.51 0.52
Анализ сложности:
- Сложность в наихудшем случае: O(n2)
Наихудший случай возникает, когда наибольшее количество элементов помещается в одно ведро. Если для сортировки элементов сегмента используется алгоритм сортировки вставками, временная сложность становится O(n2). - Сложность в наилучшем случае: O(n+k).
Временная сложность в наилучшем случае возникает, когда элементы массива равномерно распределены во всех корзинах, причем каждая корзина содержит равное количество элементов. Наилучшее время составляет O(n+k), где O(n) – сложность изготовления сегментов, а O(k) — сложность сортировки элементов ведра с помощью алгоритма, имеющего в лучшем случае линейную временную сложность.
Является ли сортировка ведром стабильной?
Определение стабильного: сохраняется или сохраняется относительный порядок элементов с одинаковым значением.
Сортировка сегментов может быть или может быть стабильной в зависимости от алгоритма, используемого для сортировки элементов сегмента.
Ведущая сортировка на месте?
Он использует дополнительное пространство для сортировки элементов массива (массивов сегментов), поэтому это не алгоритм сортировки на месте.
Это все, что касается этой статьи. Спасибо, что прочитали эту статью. Надеюсь, вы поняли алгоритм Bucket-sort и его временные сложности. Вы можете прочитать другие мои полезные статьи о сортировке структуры данных.
Подпишитесь на Викрама Гупту, чтобы получить похожий контент.
Визуализация, проектирование и анализ алгоритма сортировки по основанию.
Визуализация, проектирование и анализ алгоритма сортировки подсчетом.
Ссылка: Введение в алгоритмы.
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉
- 📰 Смотрите больше контента в публикации Level Up Coding
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
