Визуализация, проектирование и анализ алгоритма сортировки по основанию.

Алгоритмы сортировки

Визуализация, проектирование и анализ алгоритма сортировки по основанию.

Полный анализ алгоритма сортировки по основанию.

Эта статья посвящена визуализации, проектированию и анализу алгоритма сортировки по основанию.

Что такое Radix sort?

Поразрядная сортировка — это алгоритм сортировки без сравнения, который сортирует элементы на основе значащих цифр от наименьшего до старшего. Это стабильный алгоритм, поскольку он использует сортировку подсчетом в качестве подпроцедуры для сортировки элементов.

Чтобы понять сортировку по основанию, вы должны знать сортировку по счету, поскольку она будет использоваться при разработке кода для сортировки по основанию.

Давайте визуализируем алгоритм сортировки по основанию, взяв пример:

Предположим, что входной массив равен [10,21,17,34,44,11,654,123]. На основе алгоритма мы отсортируем входной массив в соответствии с разрядом единицы (наименее значащая цифра) до разряда сотен (наиболее значащая цифра).

Теперь давайте посмотрим, как сортировать по основанию шаг за шагом:

1. Найдите самый большой элемент в массиве, допустим, это max. Пусть ‘d’ будет количеством цифр в max. Этот d будет использоваться для просмотра всех значащих разрядов (цифр) всех элементов массива. В случае входного массива [10,21,17,34,44,11,654,123] максимальный элемент массива равен 654, следовательно, max = 654 и количество цифр в max равно 3, поэтому d=3.
2. По сути, нам нужно выполнить 3 итерации для сортировки заданного входного массива, и в каждой итерации мы будем использовать сортировку подсчетом для сортировки на основе от наименее до наиболее значащих цифр. Каждая цифра может принимать до k возможных значений.
3. Выполнение сортировки по разряду единиц, десятков, сотен.

i) Сортировка входного массива по месту (наименее значимое место):

ii) Сортировка входного массива по разряду десятков:

iii) Сортировка входного массива по разряду сотен:

Теперь давайте разработаем алгоритм сортировки по основанию:

radixSort(arr,size)
   1. find max of input array arr. 
   2. find number of digits d in max. 
   //run the for loop for d times and each time use counting sort to sort arr elements basis on unit,ten's, hundred's etc places.
   3. for i = 1 to d
       3.1 sort the array elements according to ith place digits using countingSort.
--------------------------------------------------------------------
countingSort(array, sizeOfArr, place)
   1. k --> find largest element among dth place elements.
   2. initialize count array with all elements as zeros.
   3. for i = 0 to (size-1)
       3.1 find the total count of each unique digit in dth place of elements and store the count at ith index in the count array.
   4. for i = 0 to k
       4.1 find the cumulative sum and store it in count array itself. 
   5. for j = (size-1) to 1
       5.1 store the elements from input array to output array using index from count array.
       5.2 decrease count of each element stored by 1.

ВЫХОД:

===============Array before sorting=================
[10, 21, 17, 34, 44, 11, 654, 123]
===============Array after sorting=================
iteration no = 1 [10, 21, 11, 123, 34, 44, 654, 17]
iteration no = 2 [10, 11, 17, 21, 123, 34, 44, 654]
iteration no = 3 [10, 11, 17, 21, 34, 44, 123, 654]

Анализ сложности:

Временная сложность. Мы уже знаем, что алгоритм сортировки подсчетом принимает Θ(n+k), гдеn — количество элементов во входном массиве. иkявляется самым большим элементом среди элементов d^го разряда(разрядов единиц, десятков, сотен и т. д.) входного массива (обратите внимание, что это не самый большой элемент входного массива).

Теперь сортировка подсчетом вызывается внутри цикла for, который выполняется dраз, где d — количество цифр в самом большом элементе ( max) входного массива. Следовательно, мы можем сказать, что сортировка по основанию будет принимать Θ(d(n+k)).

Таким образом, поразрядная сортировка имеет линейную временную сложность, которая лучше, чем Ω(nlogn) алгоритмов сортировки на основе сравнения.

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

Пространственная сложность:поскольку сортировка по основанию использует сортировку с подсчетом, а сортировка с подсчетом использует вспомогательные массивы размеров n и k, гдеn — количество элементов во входном массиве, а k — самый большой элемент среди элементов d-го разряда (разряды единиц, десятков, сотен и т. д.) > входного массива (обратите внимание, что это не самый большой элемент входного массива). Следовательно, пространственная сложность сортировки по основанию равна Ω(n+k).

Стабильна ли Radix Sort?

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

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

Сортировка по основанию на месте?

Он использует дополнительное пространство для сортировки элементов массива (массивы вывода и подсчета), поэтому это не алгоритм сортировки на месте.

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

Вы можете подписаться на Викрама Гупту, чтобы получить похожий контент.

Ссылка: Введение в алгоритмы.

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:

• 👏 Хлопайте за историю и подписывайтесь на автора 👉
• 📰 Смотрите больше контента в публикации Level Up Coding
• 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"

🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу