Алгоритм сортування Radix

Зміст

Як працює сортування Radix?
Алгоритм сортування Radix
Приклади Python, Java та C / C ++
Складність
Засоби сортування Radix

У цьому посібнику ви дізнаєтесь, як працює сортування radix. Крім того, ви знайдете робочі приклади сортування radix у C, C ++, Java та Python.

Сортування Radix - це техніка сортування, яка сортує елементи, спочатку групуючи окремі цифри того самого значення місця . Потім відсортуйте елементи за порядком їх збільшення / зменшення.

Припустимо, у нас є масив з 8 елементів. Спочатку ми будемо сортувати елементи на основі значення одиниці місця. Потім ми будемо сортувати елементи на основі значення десятого місця. Цей процес триває до останнього важливого місця.

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

Робота сорту Radix

Перш ніж читати цю статтю, пройдіть сортування підрахунку, оскільки підрахунок сортування використовується як проміжне сортування в сортуванні 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 є непорівняльним алгоритмом, воно має переваги перед порівняльним алгоритмами сортування.

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

Тут dє числовий цикл і O(n+k)часова складність підрахунку сортування.

Таким чином, сортування radix має лінійну часову складність, яка є кращою, ніж O(nlog n)порівняльні алгоритми сортування.

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

Це робить простір сортування radix неефективним. Ось чому цей сорт не використовується в бібліотеках програмного забезпечення.