СОРТИРАЙТЕ RADIX - УРОК ЗА DS

В тази статия ще обсъдим алгоритъма за сортиране по Radix. Radix sort е алгоритъмът за линейно сортиране, който се използва за цели числа. При сортирането по Radix се извършва сортиране цифра по цифра, което започва от най-малката до най-значимата цифра.

Процесът на радикално сортиране работи подобно на сортирането на имената на учениците според азбучния ред. В този случай има 26 основи, образувани поради 26-те азбуки на английски език. При първото преминаване имената на учениците се групират по възходящ ред на първата буква от имената им. След това при второто преминаване имената им се групират по възходящ ред на втората буква от името им. И процесът продължава, докато не намерим сортирания списък.

добавяне на java низ

Сега нека видим алгоритъма за сортиране по 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.

Стъпките, използвани при сортирането на радикално сортиране, са изброени както следва -

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

Сега нека видим работата на сортирането по радикс в детайли, като използваме пример. За да го разберем по-ясно, нека вземем несортиран масив и се опитаме да го сортираме с помощта на радикално сортиране. Това ще направи обяснението по-ясно и лесно.

В дадения масив най-големият елемент е 736 Това има 3 цифри в него. Така че цикълът ще се изпълнява до три пъти (т.е. до стотици място ). Това означава, че са необходими три преминавания за сортиране на масива.

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

Проход 1:

При първото преминаване списъкът се сортира на базата на цифрите на мястото на 0.

След първото преминаване елементите на масива са -

ъглов материал

Проход 2:

При това преминаване списъкът се сортира на базата на следващите значими цифри (т.е. цифри на 10^thмясто).

След второто преминаване елементите на масива са -

Проход 3:

При това преминаване списъкът се сортира на базата на следващите значими цифри (т.е. цифри на 100^thмясто).

След третото преминаване елементите на масива са -

Сега масивът е сортиран във възходящ ред.

Сложност на сортиране по Radix

Сега нека видим времевата сложност на сортирането по Radix в най-добрия случай, средния случай и най-лошия случай. Ще видим и космическата сложност на Radix sort.

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 sort

Сега, нека видим програмите на Radix sort в различни езици за програмиране.

програма: Напишете програма за реализиране на 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

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