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

В този урок ще научите как работи сортирането по radix. Също така ще намерите работещи примери за сортиране на radix в C, C ++, Java и Python.

Сортирането по Radix е техника за сортиране, която сортира елементите, като първо групира отделните цифри на една и съща стойност . След това сортирайте елементите според техния ред на увеличаване / намаляване.

Да предположим, че имаме масив от 8 елемента. Първо ще сортираме елементи въз основа на стойността на единичното място. След това ще сортираме елементи въз основа на стойността на десетото място. Този процес продължава до последното значимо място.

Нека първоначалният масив да бъде (121, 432, 564, 23, 1, 45, 788). Той се сортира според сортиране по радикс, както е показано на фигурата по-долу.

Работа на Radix Sort

Моля, преминете през сортирането за броене, преди да прочетете тази статия, защото сортирането за броене се използва като междинно сортиране в сортиране по radix.

Как работи сортирането на Radix?

Намерете най-големия елемент в масива, т.е. макс. Позволете Xда бъде броят на цифрите в max. Xсе изчислява, защото трябва да преминем през всички значими места на всички елементи.
В този масив (121, 432, 564, 23, 1, 45, 788)имаме най-голямото число 788. Той има 3 цифри. Следователно цикълът трябва да стигне до стотици място (3 пъти).
Сега преминете през всяко важно място едно по едно.
Използвайте всяка стабилна техника за сортиране, за да сортирате цифрите на всяко важно място. За това използвахме сортиране на броенето.
Сортирайте елементите въз основа на цифрите за единично място ( X=0). Използване на сортиране на броене за сортиране на елементи въз основа на единично място
Сега сортирайте елементите въз основа на цифри на десетки. Сортиране на елементи въз основа на десетки места
И накрая, сортирайте елементите въз основа на цифрите на стотици. Сортиране на елементи въз основа на стотици място

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

 radixSort (масив) d <- максимален брой цифри в най-големия елемент създават d кофи с размер 0-9 за i <- 0 до d сортират елементите според i-то място цифри, използвайки countingSort countingSort (масив, d) max <- намери най-големият елемент сред елементите от d-то място инициализира масив за броене с всички нули за j <- 0 за размер намери общия брой на всяка уникална цифра в d-то място на елементите и съхранява броя при j-тия индекс в масива за брой за i <- 1 до макс. намиране кумулативната сума и я съхранявайте в самия масив count за j <- размер до 1 възстановяване на елементите в масив намаляване брой на всеки елемент възстановен с 1

Примери за Python, Java и C / C ++

Python Java C C ++

 # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)

 // Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )

 // Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i  = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )

Сложност

Тъй като radix сортирането е несравнителен алгоритъм, той има предимства пред сравнителните алгоритми за сортиране.

За корен вид, който използва преброяване подредени като междинен стабилен вид, сложността време е O(d(n+k)).

Тук dе числовият цикъл и O(n+k)е времевата сложност на преброяването на сортирането.

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

Ако вземем много големи цифри или броя на други бази като 32-битови и 64-битови числа, тогава той може да изпълнява в линейно време, но междинното сортиране отнема голямо пространство.

Това прави пространството за сортиране по radix неефективно. Това е причината този сорт да не се използва в софтуерните библиотеки.