Algoritam sortiranja Radix

U ovom vodiču naučit ćete kako radix sortiranje djeluje. Također ćete pronaći radne primjere radix sortiranja u C, C ++, Java i Python.

Radix sortiranje je tehnika sortiranja koja razvrstava elemente prvo grupiranjem pojedinačnih znamenki iste vrijednosti mjesta . Zatim sortirajte elemente prema redoslijedu povećavanja / smanjivanja.

Pretpostavimo da imamo niz od 8 elemenata. Prvo ćemo razvrstati elemente na temelju vrijednosti jedinice jedinice. Zatim ćemo razvrstati elemente na temelju vrijednosti desetog mjesta. Taj se postupak odvija do posljednjeg značajnog mjesta.

Neka početni niz bude (121, 432, 564, 23, 1, 45, 788). Sortirano je prema radix sortiranju kao što je prikazano na donjoj slici.

Rad Radix Sort-a

Prije čitanja ovog članka, prođite kroz sortiranje brojanja jer se sortiranje brojanja koristi kao posredna sortiranja u radix sortiranju.

Kako radi Radix Sort?

  1. Pronađite najveći element u polju, tj. Maks. Dopustite Xbroj znamenki u max. Xizračunava se jer moramo proći kroz sva značajna mjesta svih elemenata.
    U ovom polju (121, 432, 564, 23, 1, 45, 788)imamo najveći broj 788. Ima 3 znamenke. Stoga bi petlja trebala ići na stotine mjesta (3 puta).
  2. Sada, prođite svako značajno mjesto jedno po jedno.
    Upotrijebite bilo koju stabilnu tehniku ​​sortiranja za razvrstavanje znamenki na svakom značajnom mjestu. Za ovo smo koristili sortiranje brojanja.
    Razvrstajte elemente na temelju znamenki mjesta ( X=0). Korištenje sortiranja brojanjem za sortiranje elemenata na temelju jedinice jedinice
  3. Sada sortirajte elemente na temelju znamenki na desetinama mjesta. Poredaj elemente na temelju desetica mjesta
  4. Na kraju, razvrstajte elemente na temelju znamenki na stotine mjesta. Poredaj elemente na temelju stotina mjesta

Algoritam sortiranja Radix

 radixSort (array) d <- maksimalan broj znamenki u najvećem elementu stvori d segmenata veličine 0-9 za i <- 0 do d sortiranje elemenata prema znamenkama i-tog mjesta pomoću countingSort countingSort (array, d) max <- pronađi najveći element među elementima d-tog mjesta inicijalizira niz niza sa svim nulama za j <- 0 za veličinu pronađi ukupan broj svake jedinstvene znamenke na d-tom mjestu elemenata i pohrani brojanje po j-tom indeksu u nizu brojeva za i <- 1 do max pronađi kumulativni zbroj i pohranite ga u sam niz niza za j <- veličina do 1 obnovi elemente u niz smanji broj svakog elementa vraćenog za 1

Primjeri Pythona, Java i 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); )

Složenost

Budući da je radix sortiranje neusporedni algoritam, ima prednosti u odnosu na usporedne algoritme sortiranja.

Za radix sortiranje koje koristi brojanje sortiranja kao srednje stabilnu sortiranje, vremenska je složenost O(d(n+k)).

Ovdje dje ciklus brojeva i O(n+k)vremenska složenost brojanja sortiranja.

Dakle, radix sortiranje ima linearnu vremensku složenost koja je bolja od O(nlog n)usporedne algoritme sortiranja.

Ako uzmemo vrlo velike znamenkaste brojeve ili broj drugih baza kao što su 32-bitni i 64-bitni brojevi, tada se može izvoditi u linearnom vremenu, međutim međuredna sorta zauzima velik prostor.

To čini prostor sortiranja radix neučinkovitim. To je razlog zašto se ova vrsta ne koristi u knjižnicama softvera.

Aplikacije za sortiranje Radix

Radix sort implementiran je u

  • DC3 algoritam (Kärkkäinen-Sanders-Burkhardt) tijekom izrade niza sufiksa.
  • mjesta na kojima ima brojeva u velikim rasponima.

Zanimljivi članci...