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

В этом руководстве вы узнаете, как работает поразрядная сортировка. Также вы найдете рабочие примеры поразрядной сортировки в C, C ++, Java и Python.

Radix сортировки сортировки техника , которая сортирует элементы по первой группировке отдельных цифр одного и того же значения места . Затем отсортируйте элементы в соответствии с их порядком увеличения / уменьшения.

Допустим, у нас есть массив из 8 элементов. Сначала мы отсортируем элементы на основе значения единицы места. Затем мы отсортируем элементы по значению десятого места. Этот процесс продолжается до последнего значимого места.

Пусть исходный массив будет (121, 432, 564, 23, 1, 45, 788). Он сортируется по основанию системы счисления, как показано на рисунке ниже.

Работа Radix Sort

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

Как работает Radix Sort?

  1. Найдите самый большой элемент в массиве, т.е. макс. Позвольте Xбыть количество цифр в max. Xрассчитывается, потому что мы должны пройти все значимые места всех элементов.
    В этом массиве (121, 432, 564, 23, 1, 45, 788)у нас есть наибольшее число 788. Оно состоит из 3 цифр. Следовательно, петля должна доходить до сотен разряда (3 раза).
  2. Теперь пройдитесь по каждому значимому месту по одному.
    Используйте любую стабильную технику сортировки, чтобы отсортировать цифры в каждом значимом месте. Для этого мы использовали счетную сортировку.
    Отсортируйте элементы по разряду цифр ( X=0). Использование подсчетной сортировки для сортировки элементов по месту расположения
  3. Теперь отсортируйте элементы на основе цифр в разряде десятков. Сортировка элементов по разряду десятков
  4. Наконец, отсортируйте элементы на основе цифр в разрядах сотен. Сортировка элементов по сотням

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

 radixSort (array) d <- максимальное количество цифр в самом большом элементе создать d сегментов размером 0-9 для i <- 0, чтобы d отсортировать элементы в соответствии с i-м разрядами, используя countingSort countingSort (array, d) max <- find самый большой элемент среди элементов d-го места инициализирует массив count со всеми нулями для j <- 0 для размера найдите общее количество каждой уникальной цифры в d-м месте элементов и сохраните счетчик в j-м индексе в массиве count для i <- 1 до max find накопительную сумму и сохраните ее в самом массиве 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); )

Сложность

Поскольку поразрядная сортировка не является сравнительным алгоритмом, она имеет преимущества перед алгоритмами сравнительной сортировки.

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

Здесь d- числовой цикл и O(n+k)- временная сложность сортировки подсчетом.

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

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

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

Приложения Radix Sort

Радиксная сортировка реализована в

  • Алгоритм DC3 (Kärkkäinen-Sanders-Burkhardt) при создании массива суффиксов.
  • места, где есть числа в большом диапазоне.

Интересные статьи...