Radixi sortimisalgoritm

Selles õpetuses saate teada, kuidas radixi sortimine töötab. Samuti leiate toimivaid näiteid radix-sortimisest C, C ++, Java ja Python.

Radix omamoodi on sorteerimine tehnikat, mis sorteerib elemente esmalt rühmitades üksikud numbrit sama väärus . Seejärel sorteerige elemendid nende kasvava / kahaneva järjekorra järgi.

Oletame, et meil on 8 elemendi massiiv. Esiteks sorteerime elemendid ühikukoha väärtuse põhjal. Seejärel sorteerime elemendid kümnenda koha väärtuse põhjal. See protsess kestab kuni viimase märkimisväärse kohani.

Olgu algne massiiv (121, 432, 564, 23, 1, 45, 788). See on sorteeritud vastavalt radix-sortimisele, nagu on näidatud alloleval joonisel.

Radix Sort töötab

Enne selle artikli lugemist lugege läbi loendamissordi, sest loendussorte kasutatakse radiksi sortimisel vahesordina.

Kuidas Radix Sort töötab?

  1. Leidke massiivi suurim element, st max. Laskma Xolema number numbrit max. Xarvutatakse, kuna peame läbima kõigi elementide kõik olulised kohad.
    Selles massiivis (121, 432, 564, 23, 1, 45, 788)on meil suurim arv 788. Sellel on 3 numbrit. Seetõttu peaks silmus tõusma sadadesse kohtadesse (3 korda).
  2. Nüüd läbige iga märkimisväärne koht ükshaaval.
    Numbrite sortimiseks igas olulises kohas kasutage mis tahes stabiilset sorteerimistehnikat. Oleme selleks kasutanud loendussorteerimist.
    Sorteeri elemendid ühiku koha numbrite ( X=0) alusel. Loendamissordi kasutamine elementide sortimiseks üksuse koha järgi
  3. Nüüd sorteerige elemendid kümnete kohtade arvu järgi. Sorteeri elemente kümnete koha järgi
  4. Lõpuks sorteerige elemendid sadade kohtade arvu järgi. Sorteeri elemente sadade kohtade järgi

Radixi sortimisalgoritm

 radixSort (massiiv) d <- suurima elemendi numbrite maksimaalne arv loob d ämbrid suurusega 0-9 i <- 0 jaoks, et d sorteerida elemendid i-de kohanumbrite järgi, kasutades countingSort countingSort (massiiv, d) max <- leia suurim element d-koha elemendi hulgast initsialiseerib loendusmassiivi kõigi nullidega suuruseks j <- 0 suuruse leidmiseks leidke iga kordumatu numbri kogu elementide d-ndas kohas ja salvestage arv i massi massiivis j-ndal indeksil arvuga i <- 1 kuni maksimaalne leid kumulatiivse summa ja salvestage see arv massiivi enda jaoks j <- suurus alla 1, taastage elemendid massiivi vähenemise arvu kohta iga 1 võrra

Pythoni, Java ja C / C ++ näited

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); )

Keerukus

Kuna radiksisort on mittevõrdlev algoritm, on sellel eeliseid võrreldes võrdlevate sortimisalgoritmidega.

Radiksisordi puhul, mis kasutab loendussorteerimist stabiilse vahesordina, on aja keerukus O(d(n+k)).

Siin don arvutsükkel ja O(n+k)sordi loendamise ajaline keerukus.

Seega on radiksisordil ajaline keerukus lineaarne, mis on parem kui O(nlog n)võrdlevatel sortimisalgoritmidel.

Kui võtame väga suured numbrilised numbrid või muude aluste arv, näiteks 32- ja 64-bitised numbrid, saab see toimida lineaarse ajaga, kuid vahesorteerimine võtab palju ruumi.

See muudab radixi sorteerimisruumi ebaefektiivseks. See on põhjus, miks seda sorti tarkvarakogudes ei kasutata.

Radixi rakenduste sortimine

Radixi sortimine on rakendatud aastal

  • DC3 algoritm (Kärkkäinen-Sanders-Burkhardt), tehes samas sufiksimassiivi.
  • kohad, kus on numbreid suurtes vahemikes.

Huvitavad Artiklid...