Пълен анализ на алгоритъма за сортиране Radix.
Тази статия е за визуализирането, проектирането и анализирането на алгоритъма за Radix Sort.
Какво е Radix sort?
Radix sort е алгоритъм за сортиране без сравнение, който сортира елементите въз основа на най-малките до най-значимите цифри. Това е стабилен алгоритъм, тъй като използва Counting sort като подпроцедура за сортиране на елементите.
За да разберете сортирането по Radix, имате познания за сортирането с преброяване, тъй като ще се използва при проектирането на кода за сортиране по Radix.
Нека визуализираме алгоритъма за сортиране по Radix, като вземем пример:
Да приемем, че входният масив е [10,21,17,34,44,11,654,123]. Въз основа на алгоритъма ще сортираме входния масив според мястото на единицата (най-значимата цифра) до стотната позиция (най-значимата цифра).
Сега нека видим Radix сортиране стъпка по стъпка:
- Намерете най-големия елемент в масива, да го кажем max. Нека ‘d’ е броят на цифрите в max. Това dще се използва за преминаване през всички значими места (цифри) на всички елементи на масива. В случай на входен масив [10,21,17,34,44,11,654,123], максималният елемент на масива е 654, следователноmax = 654и брой цифри в max е 3, следователно d=3.
- По принцип трябва да извършим3 итерации, за да сортираме дадения входен масив и във всяка итерация ще използваме сортиране с броене, за да сортираме въз основа на най-малките до най-значимите цифри. Всяка цифра може да приеме до k възможни стойности
- Извършване на сортиране при броене въз основа на място на едно, десет, сто.
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 и неговата времева и пространствена сложност. Можете да прочетете другите ми полезни статии за сортиране на структура на данни.
Литература: Въведение в алгоритмите.