1. Въведение
В този урок ще научим за Radix Sort, ще анализираме неговата ефективност и ще разгледаме изпълнението му.
Тук се фокусираме върху използването на Radix Sort за сортиране на цели числа, но това не се ограничава само до числа. Можем да го използваме и за сортиране на други типове като String .
За да бъде лесно, ще се съсредоточим върху десетичната система, в която числата са изразени в основа (радикс) 10.
2. Преглед на алгоритъма
Radix сортиране е алгоритъм за сортиране, който сортира числата въз основа на позициите на техните цифри. По принцип използва мястото на цифрите в число. За разлика от повечето други алгоритми за сортиране, като Merge Sort, Insertion Sort, Bubble Sort, той не сравнява числата.
Radix сортирането използва стабилен алгоритъм за сортиране като подпрограма за сортиране на цифрите. Използвахме вариант на сортиране на броене като подпрограма тук, която използва radix за сортиране на цифрите във всяка позиция. Сортирането при броене е стабилен алгоритъм за сортиране и работи добре на практика.
Radix сортирането работи чрез сортиране на цифри от най-малко значимата цифра (LSD) до най-значимата цифра (MSD). Също така можем да приложим сортиране Radix за обработка на цифри от MSD.
3. Бърз пример
Нека да видим как работи с пример. Нека разгледаме следния масив:
Повторение 1:
Ще сортираме този масив, като обработим цифри от LSD и преминем към MSD.
Затова нека започнем с цифрите на едно място:
След първата итерация масивът изглежда така:
Имайте предвид, че числата са сортирани според цифрите на едно място.
Повторение 2:
Нека да преминем към цифрите на десетки:
Сега масивът изглежда така:
Виждаме, че числото 7 е заело първата позиция в масива, тъй като няма място на десетката. Бихме могли да помислим и за това, че имаме 0 на десетки.
Повторение 3:
Нека да преминем към цифрите в позиция стотици:
След тази итерация масивът изглежда така:
И алгоритъмът спира до тук, като всички елементи са сортирани.
4. Изпълнение
Нека сега разгледаме изпълнението.
void sort(int[] numbers) { int maximumNumber = findMaximumNumberIn(numbers); int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber); int placeValue = 1; while (numberOfDigits-- > 0) { applyCountingSortOn(numbers, placeValue); placeValue *= 10; } }Алгоритъмът работи, като открива максималния брой в масива и след това изчислява дължината му. Тази стъпка ни помага да гарантираме, че изпълняваме подпрограмата за всяка стойност на място.
Например в масива [7, 37, 68, 123, 134, 221, 387, 468, 769] максималният брой е 769, а дължината му е 3.
И така, ние итерираме и прилагаме подпрограмата три пъти върху цифрите във всяка позиция:
void applyCountingSortOn(int[] numbers, int placeValue) { int range = 10 // decimal system, numbers from 0-9 // ... // calculate the frequency of digits for (int i = 0; i < length; i++) { int digit = (numbers[i] / placeValue) % range; frequency[digit]++; } for (int i = 1; i
= 0; i--) { int digit = (numbers[i] / placeValue) % range; sortedValues[frequency[digit] - 1] = numbers[i]; frequency[digit]--; } System.arraycopy(result, 0, numbers, 0, length); }
В подпрограмата използвахме radix (диапазон), за да преброим появата на всяка цифра и да увеличим нейната честота. И така, всеки контейнер в диапазона от 0 до 9 ще има някаква стойност въз основа на честотата на цифрите. След това използваме честотата, за да позиционираме всеки елемент в масива. Това също ни помага да сведем до минимум пространството, необходимо за сортиране на масива.
Сега нека тестваме нашия метод:
@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted() { int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort(numbers); int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals(numbersSorted, numbers); }5. Сортиране по Radix срещу Сортиране при броене
В подпрограмата дължината на честотния масив е 10 (0-9). В случая на Counting Sort не използваме диапазона . Дължината на честотния масив ще бъде максималният брой в масива + 1. Така че не ги разделяме на кошчета, докато Radix Sort използва контейнерите за сортиране.
Counting Sort е доста ефективен, когато дължината на масива не е много по-малка от максималната стойност в масива, докато Radix Sort позволява по-големи стойности в масива.
6. Сложност
Ефективността на Radix Sort зависи от стабилния алгоритъм за сортиране, избран за сортиране на цифрите.
Тук използвахме сорта Radix за сортиране на масив от n числа в база b . В нашия случай основата е 10. Приложихме Сортиране на броене d пъти, където d означава броят на цифрите. Така сложността във времето на Radix Sort става O (d * (n + b)) .
Космическата сложност е O (n + b), тъй като тук сме използвали вариант на сортиране на преброяване като подпрограма.
7. Заключение
В тази статия описахме алгоритъма за сортиране Radix и илюстрирахме как да го приложим.
Както обикновено, реализациите на кода са достъпни в Github.