Sorter Radix er en lineær sorteringsalgoritme som sorterer elementer ved å behandle dem siffer for siffer. Det er en effektiv sorteringsalgoritme for heltall eller strenger med nøkler med fast størrelse.
I stedet for å sammenligne elementer direkte, distribuerer Radix Sort elementene i bøtter basert på hvert siffers verdi. Ved å gjentatte ganger sortere elementene etter deres signifikante sifre, fra den minst signifikante til den mest signifikante, oppnår Radix Sort den endelige sorterte rekkefølgen.
Radix sorteringsalgoritme
Nøkkelideen bak Radix Sort er å utnytte konseptet stedsverdi. Den forutsetter at sortering av tall siffer for siffer til slutt vil resultere i en fullstendig sortert liste. Radix-sortering kan utføres ved hjelp av forskjellige varianter, for eksempel Least Significant Digit (LSD) Radix Sort eller Most Significant Digit (MSD) Radix Sort.
Hvordan fungerer Radix Sort Algorithm?
For å utføre radiksortering på matrisen [170, 45, 75, 90, 802, 24, 2, 66], følger vi disse trinnene:
Hvordan fungerer Radix Sort Algorithm | Trinn 1
Trinn 1: Finn det største elementet i matrisen, som er 802. Det har tre sifre, så vi vil iterere tre ganger, en gang for hvert betydelig sted.
Steg 2: Sorter elementene basert på enhetsplasseringssifrene (X=0). Vi bruker en stabil sorteringsteknikk, for eksempel tellesortering, for å sortere sifrene på hvert betydelig sted.
mvc i vårrammeSortering basert på enhetssted:
- Utfør tellesortering på matrisen basert på enhetsplasseringssifrene.
- Den sorterte matrisen basert på enhetsplassen er [170, 90, 802, 2, 24, 45, 75, 66].
Hvordan fungerer Radix Sort Algorithm | Steg 2
Trinn 3: Sorter elementene basert på sifrene for tiplasser.
Sortering basert på tierplassen:
- Utfør tellesortering på matrisen basert på sifrene for tiere.
- Den sorterte matrisen basert på tierplassen er [802, 2, 24, 45, 66, 170, 75, 90].
Hvordan fungerer Radix Sort Algorithm | Trinn 3
Trinn 4: Sorter elementene basert på hundrevis av plasssifrene.
Sortering basert på hundrevis av plass:
- Utfør tellesortering på matrisen basert på hundrevis av plasssifrene.
- Den sorterte matrisen basert på hundreplassen er [2, 24, 45, 66, 75, 90, 170, 802].
Hvordan fungerer Radix Sort Algorithm | Trinn 4
Trinn 5: Matrisen er nå sortert i stigende rekkefølge.
android.process.acore fortsetter å stoppeDen endelige sorterte matrisen som bruker radix-sortering er [2, 24, 45, 66, 75, 90, 170, 802].
Hvordan fungerer Radix Sort Algorithm | Trinn 5
Nedenfor er implementeringen for illustrasjonene ovenfor:
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]; returnere mx; } // En funksjon for å telle slags arr[] // i henhold til sifferet // representert av exp. void countSort(int arr[], int n, int exp) { // Output array int output[n]; int i, count[10] = { 0 }; // Lagre antall forekomster // i antall[] 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[antall[(arr[i] / exp) % 10] - 1] = arr[i]; telle[(arr[i] / exp) % 10]--; } // Kopier utdatamatrisen til arr[], // slik at arr[] nå inneholder sorterte // tall i henhold til gjeldende siffer for (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); } // En verktøyfunksjon for å skrive ut en array 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]; returnere mx; } // En funksjon for å telle slags arr[] i henhold til // sifferet representert av exp. statisk void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // output array int i; int count[] = new int[10]; Arrays.fill(count, 0); // Lagre antall forekomster i antall[] 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[antall[(arr[i] / exp) % 10] - 1] = arr[i]; telle[(arr[i] / exp) % 10]--; } // Kopier utdatamatrisen til arr[], slik at arr[] nå // inneholder sorterte tall i henhold til gjeldende // siffer for (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); } // En verktøyfunksjon for å skrive ut en matrise statisk 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 # Kopierer utdatamatrisen til arr[] , # slik at arr nå inneholder sorterte tall i = 0 for i i området(0, len(arr)): arr[i] = output[i] # Metode for å gjøre Radix Sort def radixSort(arr): # Finn maksimum antall å vite antall sifre max1 = max(arr) # Gjør tellesort for hvert siffer. Legg merke til at i stedet for # for bestått siffernummer, blir exp bestått. exp er 10^i # der i er gjeldende siffernummer exp = 1 mens max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Driverkode arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funksjon Call radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # Denne koden er bidratt med Mohit Kumra # Redigert av Patrick Gallagher>
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]; returnere mx; } // En funksjon for å telle slags arr[] i henhold til // sifferet representert av exp. offentlig statisk void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // output array int i; int[] count = new int[10]; // initialiserer alle elementer av telle til 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[antall[(arr[i] / exp) % 10] - 1] = arr[i]; telle[(arr[i] / exp) % 10]--; } // Kopier utdatamatrisen til arr[], slik at arr[] nå // inneholder sorterte tall i henhold til gjeldende // siffer for (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); } // En verktøyfunksjon for å skrive ut en matrise 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]; } returner mx; } // En funksjon for å telle slags arr[] i henhold til // sifferet representert av exp. function countSort(arr, exp) { const length = arr.length; la utgang = Array(lengde); // output array let count = Array(10).fill(0, 0); // Lagre antall forekomster i antall[] for (la 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; utgang[antall[siffer] - 1] = arr[i]; telle[siffer]--; } returnere utgang; } // Hovedfunksjonen til som sorterer arr[] ved hjelp av Radix Sorteringsfunksjonen radixSort(arr) { // Finn det maksimale antallet for å vite antall sifre const maxNumber = getMax(arr); // Lag en grunn kopi der de sorterte verdiene vil bli holdt la sortedArr = [...arr]; // Gjør tellesortering for hvert siffer. Merk at // i stedet for å bestå siffernummer, er exp bestått. // exp er 10^i der i er gjeldende siffernummer for (la exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Få Count sort iteration const sortedIteration = countSort(sortedArr) , exp); sortedArr = sortedIteration; } return sortedArr; } /*Sjåførkode*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funksjon Call const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Denne koden er bidratt av 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--) { $output[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // Kopier utdatamatrisen til arr[], så // at arr[] nå inneholder sorterte tall // i henhold til gjeldende siffer for ($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); } // En verktøyfunksjon for å skrive ut en matrisefunksjon 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 ?>> Dart // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List array) { int max = array[0]; for (final it in array) { if (it> max) { max = it; } } retur maks; } /// En funksjon for å telle en slags `List` [array] i henhold til ///-sifferet representert av [exp]. Liste countSort(Liste array, int exp) { endelig lengde = array.length; final outputArr = List.filled(length, 0); // En liste der indeksen representerer sifferet og verdien representerer antallet // forekomster final digitsCount = List.filled(10, 0); // Lagre antall forekomster i sifferCount[] for (endelig element i array) { final digit = item ~/ exp % 10; digitsCount[siffer]++; } // Endre sifferCount[i] slik at digitsCount[i] nå inneholder faktisk posisjon // av dette sifferet 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--) { siste element = array[i]; siste siffer = element ~/ exp % 10; outputArr[digitsCount[siffer] - 1] = vare; sifferTell[siffer]--; } returner outputArr; } /// Hovedfunksjonen som sorterer en `List` [array] ved hjelp av Radix sorteringsliste radixSort(Liste array) { // Finn det maksimale antallet for å vite antall sifre final maxNumber = getMax(array); // Grunn kopi av inndatamatrisen final sortedArr = List.of(array); // Gjør tellesortering for hvert siffer. Legg merke til at i stedet for å bestå siffer // nummer, blir exp bestått. exp er 10^i, der i er gjeldende siffernummer for (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]; final sortedArray = radixSort(array); print(sortertArray); } // Denne koden er bidratt av beeduhboodee>
Produksjon
2 24 45 66 75 90 170 802>
Kompleksitetsanalyse av Radix Sort :
Tidskompleksitet:
- Radix sort er en ikke-komparativ heltallssorteringsalgoritme som sorterer data med heltallsnøkler ved å gruppere nøklene etter de individuelle sifrene som deler samme signifikante posisjon og verdi. Den har en tidskompleksitet på O(d * (n + b)) , hvor d er antall siffer, n er antall elementer, og b er basisen til tallsystemet som brukes.
- I praktiske implementeringer er radix-sortering ofte raskere enn andre sammenligningsbaserte sorteringsalgoritmer, for eksempel quicksort eller merge sort, for store datasett, spesielt når nøklene har mange sifre. Imidlertid vokser tidskompleksiteten lineært med antall sifre, og derfor er den ikke like effektiv for små datasett.
Hjelpeplass:
binært tre java
- Radix sort har også en plasskompleksitet på O(n + b), hvor n er antall elementer og b er basisen til tallsystemet. Denne plasskompleksiteten kommer fra behovet for å lage bøtter for hver sifferverdi og å kopiere elementene tilbake til den opprinnelige matrisen etter at hvert siffer er blitt sortert.
Ofte stilte spørsmål om RadixSort
Q1. Er Radix Sort å foretrekke fremfor sammenligningsbaserte sorteringsalgoritmer som Quick-Sort?
Hvis vi har logg2n biter for hvert siffer, ser kjøretiden til Radix ut til å være bedre enn hurtigsortering for et bredt spekter av inndatanumre. De konstante faktorene som er skjult i asymptotisk notasjon er høyere for Radix Sort og Quick-Sort bruker maskinvarecacher mer effektivt. Radix sort bruker også tellesortering som en subrutine, og tellesortering tar ekstra plass for å sortere tall.
Q2. Hva om elementene er i varierer fra 1 til n 2 ?
- Den nedre grensen for den sammenligningsbaserte sorteringsalgoritmen (Merge Sort, Heap Sort, Quick-Sort .. etc) er Ω(nLogn), dvs. de kan ikke gjøre det bedre enn nLogg inn . Tellesortering er en lineær tidssorteringsalgoritme som sorterer i O(n+k) tid når elementer er i området fra 1 til k.
- Vi kan ikke bruke tellesortering fordi tellesortering vil ta O(n2) som er verre enn sammenligningsbaserte sorteringsalgoritmer. Kan vi sortere en slik matrise i lineær tid?
- Sorter Radix er svaret. Ideen med Radix Sort er å sortere siffer for siffer fra det minst signifikante sifferet til det mest signifikante sifferet. Radix sort bruker tellesortering som en subrutine for å sortere.