СОРТУВАННЯ RADIX - ПІДРУЧНИК DS

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

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

відмінність тигра і лева

Тепер давайте подивимося на алгоритм сортування Radix.

Алгоритм

 radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -&gt; 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place

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

Тепер давайте подивимося, як працює алгоритм сортування Radix.

Нижче наведено кроки, які використовуються для сортування за принципом сортування:

Спочатку ми повинні знайти найбільший елемент (припустимо макс ) із заданого масиву. Припустимо 'x' бути кількістю цифр у макс . The 'x' розраховується, тому що нам потрібно пройти значущі місця всіх елементів.
Після цього пройдіть по одному кожне значуще місце. Тут ми повинні використовувати будь-який стабільний алгоритм сортування для сортування цифр кожного значущого місця.

Тепер давайте детально розглянемо роботу принципового сортування на прикладі. Щоб зрозуміти це більш чітко, давайте візьмемо несортований масив і спробуємо відсортувати його за допомогою сортування за принципом. Це зробить пояснення зрозумілішим і легшим.

У заданому масиві найбільший елемент 736 що мають 3 цифр у ньому. Отже, цикл виконуватиметься до трьох разів (тобто до сотні місце ). Це означає, що для сортування масиву потрібні три проходи.

Тепер спочатку відсортуйте елементи на основі одиничних розрядних цифр (тобто х = 0 ). Тут ми використовуємо алгоритм сортування підрахунком для сортування елементів.

Прохід 1:

Під час першого проходу список сортується на основі цифр, що стоять на місці 0.

Після першого проходу елементи масиву -

Перехід 2:

Під час цього проходу список сортується на основі наступних значущих цифр (тобто цифр у 10^тисмісце).

Після другого проходу елементи масиву -

Прохід 3:

У цьому проході список сортується на основі наступних значущих цифр (тобто цифр у 100^тисмісце).

програма простих чисел на java

Після третього проходу елементи масиву -

Тепер масив відсортовано в порядку зростання.

Складність сортування за принципом

Тепер давайте подивимося на часову складність сортування Radix у найкращому, середньому та гіршому випадку. Ми також побачимо просторову складність сортування Radix.

1. Складність часу

Справа	Складність часу
Кращий випадок	Ω(n+k)
Середній випадок	θ(nk)
Найгірший випадок	O(nk)

Ω(n+k)

θ(nk)

O(nk)

Radix sort — це непорівняльний алгоритм сортування, який кращий за порівняльні алгоритми сортування. Він має лінійну часову складність, яка краща, ніж порівняльні алгоритми зі складністю O(n logn).

2. Просторова складність

Космічна складність	O(n + k)
Стабільний	ТАК

Просторова складність сортування Radix дорівнює O(n + k).

Реалізація сортування Radix

Тепер давайте подивимося на програми сортування Radix на різних мовах програмування.

програма: Напишіть програму для реалізації сортування Radix мовою C.

 #include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarray(a,n); radixsort(a, n); cout<<'

after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); console.write('

after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are - 
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('

after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>

TechCodeview

Алгоритм сортування за принципом