Radix algoritam sortiranja u strukturi podataka
Što je Radix algoritam sortiranja?
Radix Sort je neusporedni algoritam sortiranja. Djeluje tako da grupira pojedinačne znamenke elemenata koje treba sortirati. Zatim se koristi stabilna tehnika sortiranja za organiziranje elemenata na temelju njihovog radiksa. To je linearni algoritam sortiranja.
Proces sortiranja uključuje sljedeća svojstva:
- Pronalaženje maksimalnog elementa i dobivanje broja znamenki tog elementa. Daje nam broj ponavljanja koje će proces sortiranja slijediti.
- Grupirajte pojedinačne znamenke elemenata na istoj značajnoj poziciji u svakoj iteraciji.
- Proces grupiranja započet će od najmanje značajne znamenke i završiti na najznačajnijoj znamenki.
- Razvrstavanje elemenata na temelju znamenki na toj značajnoj poziciji.
- Održavanje relativnog poretka elemenata koji imaju istu ključnu vrijednost. Ovo svojstvo radikalne sorte čini je stabilnom sortom.
Konačna iteracija će nam dati potpuno sortirani popis.
Rad algoritma radix sortiranja
Pokušajmo sortirati popis cijelih brojeva na gornjoj slici uzlaznim redoslijedom pomoću algoritma Radix Sort.
Evo koraka za izvođenje postupka radix sortiranja:
Korak 1) Identificirajte element s najvećom vrijednošću na popisu. U ovom slučaju to je 835.
Korak 2) Izračunajte broj znamenki maksimalnog elementa. 835 ima točno 3 znamenke.
Korak 3) Odredite broj ponavljanja na temelju koraka 2. 835 ima 3 znamenke, što znači da će broj ponavljanja biti 3.
Korak 4) Odredite bazu elemenata. Budući da je ovo decimalni sustav, baza će biti 10.
Korak 5) Započnite prvu iteraciju.
a) Prva iteracija
U prvoj iteraciji razmatramo jediničnu vrijednost svakog elementa.
Korak 1) Modificirajte cijeli broj za 10 da dobijete mjesto jedinice elemenata. Na primjer, 623 mod 10 daje nam vrijednost 3, a 248 mod 10 daje nam 8.
Korak 2) Upotrijebite sortiranje brojanjem ili bilo koje drugo stabilno sortiranje da organizirate cijele brojeve prema njihovoj najmanje značajnoj znamenki. Kao što se vidi sa slike, 248 će pasti na 8. kantu. 623 će pasti na 3. kantu i tako dalje.
Nakon prve iteracije lista sada izgleda ovako.
Kao što možete vidjeti na gornjoj slici, popis još nije sortiran i zahtijeva više ponavljanja da bi bio u potpunosti sortiran.
b) Druga iteracija
U ovoj iteraciji, razmotrit ćemo znamenku na 10th mjesto za proces sortiranja.
Korak 1) Podijelite cijele brojeve s 10. 248 podijeljeno s 10 daje nam 24.
Korak 2) Izmijenite izlaz koraka 1 za 10. 24 mod 10 daje nam 4.
Korak 3) Slijedite korak 2 iz prethodne iteracije.
Nakon druge iteracije lista sada izgleda ovako
Na gornjoj slici možete vidjeti da lista još uvijek nije u potpunosti sortirana jer još nije u uzlaznom redoslijedu.
c) Treća iteracija
Za posljednju iteraciju, želimo dobiti najznačajniju znamenku. U ovom slučaju, to je 100th mjesto za svaki od cijelih brojeva na listi.
Korak 1) Podijelite cijele brojeve sa 100... 415 podijeljeno sa 100 daje nam 4.
Korak 2) Modificirajte rezultat iz koraka 1 za 10. 4 mod 10 opet nam daje 4.
Korak 3) Slijedite korak 3 iz prethodne iteracije.
Kao što vidimo, lista je sada poredana uzlaznim redoslijedom. Završna iteracija je završena i proces sortiranja je sada završen.
Pseudokod Radix algoritma sortiranja
Ovdje je pseudokod za Radix algoritam sortiranja
radixSortAlgo(arr as an array) Find the largest element in arr maximum=the element in arr that is the largest Find the number of digits in maximum k=the number of digits in maximum Create buckets of size 0-9 k times for j -> 0 to k Acquire the jth place of each element in arr. Here j=0 represents the least significant digit. Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace arr = sorted elements
C++ Program za implementaciju Radix sortiranja
#include <iostream> using namespace std; // Function to get the largest element in an array int getMaximum(int arr[], int n) { int maximum = arr[0]; for (int i = 1; i < n; i++) { if (maximum < arr[i]) maximum = arr[i]; } return maximum; } // We are using counting sort to sort the elements digit by digit void countingSortAlgo(int arr[], int size, int position) { const int limit = 10; int result[size]; int count[limit] = {0}; // Calculating the count of each integers for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++; // Calculating the cumulative count for (int j = 1; j < limit; j++) { count[j] += count[j - 1]; } // Sort the integers for (int j = size - 1; j >= 0; j--) { result[count[(arr[j] / position) % 10] - 1] = arr[j]; count[(arr[j] / position) % 10]--; } for (int i = 0; i < size; i++) arr[i] = result[i]; } // The radixSort algorithm void radixSortAlgo(int arr[], int size) { // Get the largest element in the array int maximum = getMaximum(arr, size); for (int position = 1; maximum / position > 0; position *= 10) countingSortAlgo(arr, size, position); } // Printing final result void printResult(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; } int main() { int arr[] = {162, 623, 835, 415, 248}; int size = sizeof(arr) / sizeof(arr[0]); radixSortAlgo(arr, size); printResult(arr, size); }
Izlaz:
162 248 415 623 835
Python Program za Radix algoritam sortiranja
#Radix Sort using python def countingSortAlgo(arr, position): n = len(arr) result = [0] * n count = [0] * 10 # Calculating the count of elements in the array arr for j in range(0, n): element = arr[j] // position count[element % 10] += 1 # Calculating the cumulative count for j in range(1, 10): count[j] += count[j - 1] # Sorting the elements i = n - 1 while i >= 0: element = arr[i] // position result[count[element % 10] - 1] = arr[i] count[element % 10] -= 1 i -= 1 for j in range(0, n): arr[j] = result[j] def radixSortAlgo(arr): # Acquiring the largest element in the array maximum = max(arr) # Using counting sort to sort digit by digit position = 1 while maximum // position > 0: countingSortAlgo(arr, position) position *= 10 input = [162, 623, 835, 415, 248] radixSortAlgo(input) print(input)
Izlaz:
[162,248,415,623,835]
Analiza složenosti Radix sortiranja
Postoje dvije vrste složenosti koje treba razmotriti, prostorna složenost i vremenska složenost.
- Složenost prostora: O(n+b) gdje je n veličina niza, a b je baza koja se razmatra.
- Vremenska složenost: O(d*(n+b)) gdje je d broj znamenki najvećeg elementa u nizu.
Prostorna složenost radix sortiranja
Dvije značajke na koje se treba usredotočiti za složenost prostora
- Broj elemenata u nizu, n.
- Osnova za predstavljanje elemenata, b.
Ponekad ta baza može biti veća od veličine niza.
Ukupna složenost je stoga O(n+b).
Sljedeća svojstva elemenata na popisu mogu učiniti prostor radix sortiranja neučinkovitim:
- Elementi s velikim brojem znamenki.
- Baza elemenata je velika, poput 64-bitnih brojeva.
Vremenska složenost radix sortiranja
Možete koristiti sortiranje brojanjem kao potprogram, jer će svaka iteracija trajatie O(n+b) vrijeme. Ako postoje iteracije, ukupno vrijeme rada postaje O(d*(n+b)). Ovdje "O" označava funkciju složenosti.
Linearnost radix sortiranja
Radix sortiranje je linearno kada
- d je konstanta, gdje je d broj znamenki najvećeg elementa.
- b nije veći u velikoj mjeri u usporedbi s n.
Usporedbe Radix Sort-a s drugim usporednim algoritmima
Kao što smo vidjeli, složenost Radix sortiranja temelji se na veličini riječi ili broja. Bit će iste složenosti za prosječne i najbolje slučajeve. A to je O(d*(n+b)). Također, razlikuje se prema tehnici sortiranja koju koristite u sredini. Na primjer, možete koristiti sortiranje brojanjem ili brzo sortiranje za srednji algoritam sortiranja unutar Radix sortiranja.
Primjene Radix algoritma sortiranja
Važne primjene Radix sortiranja su:
- Radix sortiranje može se koristiti kao algoritam za pronalaženje lokacije gdje se koriste veliki rasponi vrijednosti.
- Koristi se za konstruiranje niza sufiksa u DC3 algoritmu.
- Koristi se u sekvencijalnom stroju s nasumičnim pristupom koji je prisutan u tipičnom računalu gdje se zapisi unose ključem.