Сортування Radix це лінійний алгоритм сортування, який сортує елементи, обробляючи їх цифру за цифрою. Це ефективний алгоритм сортування для цілих чисел або рядків із ключами фіксованого розміру.
Замість того, щоб безпосередньо порівнювати елементи, Radix Sort розподіляє елементи у відра на основі значення кожної цифри. Повторно сортуючи елементи за їхніми значущими цифрами, від найменш значущих до найбільш значущих, Radix Sort досягає остаточного порядку сортування.
Алгоритм сортування за принципом
Ключовою ідеєю Radix Sort є використання концепції значення місця. Припускається, що сортування чисел цифра за цифрою зрештою призведе до повного сортування списку. Сортування за основою можна виконувати за допомогою різних варіацій, наприклад сортування за основою за найменшою значущою цифрою (LSD) або сортування за основою за найголовнішою цифрою (MSD).
Як працює алгоритм сортування Radix?
Щоб виконати сортування за основою в масиві [170, 45, 75, 90, 802, 24, 2, 66], виконайте такі дії:
Як працює алгоритм сортування Radix | Крок 1
Крок 1: Знайдіть найбільший елемент у масиві, який дорівнює 802. Він має три цифри, тому ми повторимо три рази, по одному для кожного значущого місця.
крок 2: Відсортуйте елементи за розрядами одиниць (X=0). Ми використовуємо стабільну техніку сортування, наприклад сортування підрахунком, щоб сортувати цифри в кожному значущому місці.
недоліки ІнтернетуСортування за місцем одиниці:
- Виконайте підрахункове сортування в масиві на основі розрядних цифр одиниці.
- Відсортований масив на основі одиничного місця [170, 90, 802, 2, 24, 45, 75, 66].
Як працює алгоритм сортування Radix | Крок 2
крок 3: Відсортуйте елементи за розрядом десятків.
Сортування за розрядом десятків:
- Виконайте підрахункове сортування в масиві на основі розрядів десятків.
- Відсортований масив на основі розряду десятків [802, 2, 24, 45, 66, 170, 75, 90].
Як працює алгоритм сортування Radix | Крок 3
екземпляр у javaкрок 4: Відсортуйте елементи за розрядом сотень.
Сортування на основі місця сотні:
- Виконайте підрахункове сортування в масиві на основі розрядів сотень.
- Відсортований масив на основі розряду сотень [2, 24, 45, 66, 75, 90, 170, 802].
Як працює алгоритм сортування Radix | Крок 4
крок 5: Тепер масив відсортовано в порядку зростання.
Остаточний відсортований масив за допомогою сортування за основою [2, 24, 45, 66, 75, 90, 170, 802].
Як працює алгоритм сортування Radix | Крок 5
Нижче наведено реалізацію наведених вище ілюстрацій:
C++ // C++ implementation of Radix Sort #include using namespace std; // A utility function to get maximum // value in arr[] int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arr[i]; повернення mx; } // Функція для сортування підрахунку arr[] // відповідно до цифри // представленої exp. void countSort(int arr[], int n, int exp) { // Масив виводу int output[n]; int i, count[10] = { 0 }; // Зберігати кількість входжень // у count[] for (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] // now contains actual position // of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Скопіюйте вихідний масив до arr[], // щоб arr[] тепер містив відсортовані // числа відповідно до поточної цифри для (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] // of size n using Radix Sort void radixsort(int arr[], int n) { // Find the maximum number to // know number of digits int m = getMax(arr, n); // Do counting sort for every digit. // Note that instead of passing digit // number, exp is passed. exp is 10^i // where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Допоміжна функція для друку масиву void print(int arr[], int n) { for (int i = 0; i< n; i++) cout << arr[i] << ' '; } // Driver Code int main() { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call radixsort(arr, n); print(arr, n); return 0; }> Java // Radix sort Java implementation import java.io.*; import java.util.*; class Radix { // A utility function to get maximum value in arr[] static int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arr[i]; повернення mx; } // Функція для сортування підрахунку arr[] відповідно до // цифри, представленої exp. static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // вихідний масив int i; int count[] = новий int[10]; Arrays.fill(кількість, 0); // Зберігати кількість входжень у count[] for (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Скопіюйте вихідний масив до arr[], щоб arr[] тепер // містив відсортовані числа відповідно до поточної // цифри для (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of // size n using Radix Sort static void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Допоміжна функція для друку масиву static void print(int arr[], int n) { for (int i = 0; i< n; i++) System.out.print(arr[i] + ' '); } // Main driver method public static void main(String[] args) { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.length; // Function Call radixsort(arr, n); print(arr, n); } }> Python3 # Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = arr[i] // exp1 count[index % 10] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1, 10): count[i] += count[i - 1] # Build the output array i = n - 1 while i>= 0: index = arr[i] // exp1 output[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # Копіювання вихідного масиву в arr[] , # щоб arr тепер містив відсортовані числа i = 0 для i в діапазоні (0, len(arr)): arr[i] = output[i] # Метод для Radix Sort def radixSort(arr): # Знайти максимум число, щоб знати кількість цифр max1 = max(arr) # Виконати підрахункове сортування для кожної цифри. Зверніть увагу, що замість # переданого цифрового числа передається exp. exp is 10^i # де i поточний номер цифри exp = 1 тоді як max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Код драйвера arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Виклик функції radixSort(arr) для i в діапазоні (len(arr)): print(arr[i], end=' ') # Цей код надав Мохіт Кумра # Відредаговано Патріком Галлахером>
C# // C# implementation of Radix Sort using System; class GFG { public static int getMax(int[] arr, int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arr[i]; повернення mx; } // Функція для сортування підрахунку arr[] відповідно до // цифри, представленої exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // вихідний масив int i; int[] count = новий int[10]; // ініціалізація всіх елементів count до 0 for (i = 0; i< 10; i++) count[i] = 0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Скопіюйте вихідний масив до arr[], щоб arr[] тепер // містив відсортовані числа відповідно до поточної // цифри для (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort public static void radixsort(int[] arr, int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Допоміжна функція для друку масиву public static void print(int[] arr, int n) { for (int i = 0; i< n; i++) Console.Write(arr[i] + ' '); } // Driver Code public static void Main() { int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; // Function Call radixsort(arr, n); print(arr, n); } // This code is contributed by DrRoot_ }> Javascript // Radix sort JavaScript implementation 'use strict'; // A utility function to get maximum value in arr[] function getMax(arr) { const length = arr.length; let mx = arr[0]; for (let i = 1; i < length; i++) { if (arr[i]>mx) mx = arr[i]; } return mx; } // Функція для сортування підрахунку arr[] відповідно до // цифри, представленої exp. функція countSort(arr, exp) { const length = arr.length; нехай вихід = масив (довжина); // вихідний масив let count = Array(10).fill(0, 0); // Зберігати кількість входжень у count[] for (let i = 0; i< length; i++) { const digit = Math.floor(arr[i] / exp) % 10; count[digit]++; } // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (let i = 1; i < 10; i++) { count[i] += count[i - 1]; } // Build the output array for (let i = length - 1; i>= 0; i--) { const digit = Math.floor(arr[i] / exp) % 10; вихід [кількість [цифра] - 1] = arr[i]; кількість [цифра]--; } повернути вихід; } // Основна функція для сортування arr[] за допомогою Radix Sort function radixSort(arr) { // Знайти максимальне число, яке потрібно знати кількість цифр const maxNumber = getMax(arr); // Створіть поверхневу копію, де зберігатимуться відсортовані значення let sortedArr = [...arr]; // Сортування підрахунку для кожної цифри. Зауважте, що // замість передачі цифри передається exp. // exp дорівнює 10^i, де i — поточний номер цифри для (нехай exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Отримати кількість ітерації сортування const sortedIteration = countSort(sortedArr , exp); sortedArr = sortedIteration; } return sortedArr; } /*Код драйвера*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Виклик функції const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Цей код створено beeduhboodee> PHP // PHP implementation of Radix Sort // A function to do counting sort of arr[] // according to the digit represented by exp. function countSort(&$arr, $n, $exp) { $output = array_fill(0, $n, 0); // output array $count = array_fill(0, 10, 0); // Store count of occurrences in count[] for ($i = 0; $i < $n; $i++) $count[ ($arr[$i] / $exp) % 10 ]++; // Change count[i] so that count[i] // now contains actual position of // this digit in output[] for ($i = 1; $i < 10; $i++) $count[$i] += $count[$i - 1]; // Build the output array for ($i = $n - 1; $i>= 0; $i--) { $вихід[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // Скопіюйте вихідний масив до arr[], щоб // arr[] тепер містив відсортовані числа // відповідно до поточної цифри для ($i = 0; $i< $n; $i++) $arr[$i] = $output[$i]; } // The main function to that sorts arr[] // of size n using Radix Sort function radixsort(&$arr, $n) { // Find the maximum number to know // number of digits $m = max($arr); // Do counting sort for every digit. Note // that instead of passing digit number, // exp is passed. exp is 10^i where i is // current digit number for ($exp = 1; $m / $exp>0; $exp *= 10) countSort($arr, $n, $exp); } // Допоміжна функція для друку масиву function PrintArray(&$arr,$n) { for ($i = 0; $i< $n; $i++) echo $arr[$i] . ' '; } // Driver Code $arr = array(170, 45, 75, 90, 802, 24, 2, 66); $n = count($arr); // Function Call radixsort($arr, $n); PrintArray($arr, $n); // This code is contributed by rathbhupendra ?>> Дартс // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List масив) { int max = масив[0]; for (фінальний it в масиві) { if (it> max) { max = it; } } return max; } /// Функція для підрахунку сортування `List` [масив] відповідно до /// цифри, представленої [exp]. Список countSort(Список array, int exp) { final length = array.length; остаточний вихідArr = List.filled(length, 0); // Список, де індекс представляє цифру, а значення представляє кількість // входжень final digitsCount = List.filled(10, 0); // Зберігати кількість входжень у digitsCount[] for (останній елемент у масиві) { final digit = item ~/ exp % 10; digitsCount[цифра]++; } // Змінити digitsCount[i] так, щоб digitsCount[i] тепер містив фактичну позицію // цієї цифри у outputArr[] for (int i = 1; i< 10; i++) { digitsCount[i] += digitsCount[i - 1]; } // Build the output array for (int i = length - 1; i>= 0; i--) { остаточний елемент = масив[i]; кінцева цифра = item ~/ exp % 10; outputArr[digitsCount[цифра] - 1] = елемент; digitsCount[цифра]--; } return outputArr; } /// Основна функція, яка сортує `List` [масив] за допомогою Radix sort List radixSort(Список array) { // Знайдіть максимальне число, щоб знати кількість цифр final maxNumber = getMax(array); // Неглибока копія вхідного масиву final sortedArr = List.of(array); // Сортування підрахунку для кожної цифри. Зверніть увагу, що замість передачі цифри // числа передається exp. exp дорівнює 10^i, де i поточний номер цифри для (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); sortedArr.clear(); sortedArr.addAll(sortedIteration); } return sortedArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; остаточний sortedArray = radixSort(масив); print(sortedArray); } // Цей код створено beeduhboodee>
Вихід
2 24 45 66 75 90 170 802>
Аналіз складності сортування за принципом :
Часова складність:
- Сортування за принципом — це непорівняльний алгоритм цілочисельного сортування, який сортує дані за допомогою цілочисельних ключів шляхом групування ключів за окремими цифрами, які мають однакову значущу позицію та значення. Він має часову складність O(d * (n + b)) , де d — кількість цифр, n — кількість елементів, b — основа використовуваної системи числення.
- У практичних реалізаціях сортування за основою часто швидше, ніж інші алгоритми сортування на основі порівняння, такі як швидке сортування або сортування злиттям, для великих наборів даних, особливо коли ключі мають багато цифр. Однак його часова складність зростає лінійно зі збільшенням кількості цифр, тому він не такий ефективний для невеликих наборів даних.
Допоміжний простір:
- Radix sort також має просторову складність O(n + b), де n – кількість елементів, а b – основа системи числення. Ця складність простору виникає через необхідність створювати сегменти для кожного значення цифри та копіювати елементи назад у вихідний масив після того, як кожну цифру буде відсортовано.
Часті запитання про RadixSort
Q1. Чи краще сортування за принципом порівняння, ніж алгоритми сортування на основі порівняння, такі як Quick-Sort?
Якщо у нас є лог2n бітів на кожну цифру, час роботи Radix виявляється кращим, ніж Quick Sort для широкого діапазону вхідних чисел. Постійні фактори, приховані в асимптотичній нотації, вищі для Radix Sort, а Quick-Sort ефективніше використовує апаратні кеші. Крім того, сортування Radix використовує сортування підрахунком як підпрограму, а сортування підрахунком займає додатковий простір для сортування чисел.
Актриса Сай Паллаві
Q2. Що робити, якщо елементи знаходяться в діапазон від 1 до n 2 ?
- Нижня межа для алгоритму сортування на основі порівняння (сортування злиттям, сортування купи, швидке сортування тощо) становить Ω(nLogn), тобто вони не можуть працювати краще, ніж nВхід . Сортування підрахунком — це лінійний алгоритм сортування за часом, який сортує за час O(n+k), коли елементи знаходяться в діапазоні від 1 до k.
- Ми не можемо використовувати сортування підрахунком, оскільки сортування підрахунком займе O(n2), що гірше, ніж алгоритми сортування на основі порівняння. Чи можемо ми відсортувати такий масив у лінійному часі?
- Сортування Radix це відповідь. Ідея Radix Sort полягає в сортуванні цифр за цифрами, починаючи від молодшої цифри до старшої цифри. Radix сортування використовує сортування підрахунком як підпрограму сортування.