Пълен анализ на алгоритъма за сортиране Radix.

Тази статия е за визуализирането, проектирането и анализирането на алгоритъма за Radix Sort.

Какво е Radix sort?

Radix sort е алгоритъм за сортиране без сравнение, който сортира елементите въз основа на най-малките до най-значимите цифри. Това е стабилен алгоритъм, тъй като използва Counting sort като подпроцедура за сортиране на елементите.

За да разберете сортирането по Radix, имате познания за сортирането с преброяване, тъй като ще се използва при проектирането на кода за сортиране по Radix.

Нека визуализираме алгоритъма за сортиране по Radix, като вземем пример:

Да приемем, че входният масив е [10,21,17,34,44,11,654,123]. Въз основа на алгоритъма ще сортираме входния масив според мястото на единицата (най-значимата цифра) до стотната позиция (най-значимата цифра).

Сега нека видим Radix сортиране стъпка по стъпка:

  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) Сортиране на входния масив на базата на стотно място:

Сега нека проектираме алгоритъма за сортиране по Radix:

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) на входния масив. Следователно можем да кажем, че сортирането по Radix ще приеме Θ(d(n+k)).

По този начин радикалното сортиране има линейна времева сложност, която е по-добра от Ω(nlogn) на базирани на сравнение алгоритми за сортиране.

Ако вземем много големи разрядни числа, то може да работи в линейно време, но сортирането с броене заема голямо пространство. Следователно това прави пространството за сортиране на радикс неефективно.

Пространствена сложност:Тъй като Radix сортирането използва сортиране с броене, а сортирането с броене използва спомагателни масиви с размери n и k, къдетоn е броят на елементите във входния масив иkе най-големият елемент сред елементите с d-то място(единици, десетици, стотици и т.н.)от входния масив (имайте предвид, че това не е най-големият елемент от входния масив). Следователно пространствената сложност на сортирането по Radix е Ω(n+k).

Radix Sort стабилен ли е?

Дефиниция за стабилен: поддържа се относителният ред на елементи с една и съща стойност.

Radix сортирането използва стабилна процедура, която е Counting сортиране, за да сортира своите елементи от масива, следователно това също е стабилен алгоритъм.

Radix сортиране на място ли е?

Той използва допълнително пространство за сортиране на елементите на масива (масиви за изход и броене), следователно не е алгоритъм за сортиране на място.

Това е всичко за тази статия. Благодаря ви, че прочетохте тази статия. Надявам се, че сте разбрали алгоритъма за сортиране по Radix и неговата времева и пространствена сложност. Можете да прочетете другите ми полезни статии за сортиране на структура на данни.

Литература: Въведение в алгоритмите.