Tässä opetusohjelmassa opit, kuinka radix-lajittelu toimii. Löydät myös toimivia esimerkkejä radix-lajittelusta C, C ++, Java ja Python.
Radix-lajittelu on lajittelutekniikka, joka lajittelee elementit ryhmittelemällä ensin saman paikan arvon yksittäiset numerot . Lajittele sitten elementit niiden kasvavan / laskevan järjestyksen mukaan.
Oletetaan, että meillä on joukko 8 elementtiä. Ensinnäkin lajittelemme elementit yksikköpaikan arvon perusteella. Sitten lajittelemme elementit kymmenennen arvon arvon perusteella. Tämä prosessi jatkuu viimeiseen merkittävään paikkaan asti.
Olkoon ensimmäinen taulukko (121, 432, 564, 23, 1, 45, 788). Se on lajiteltu radix-lajittelun mukaan alla olevan kuvan mukaisesti.
Radix Lajittelun toiminta
Käy läpi laskemislajittelu ennen tämän artikkelin lukemista, koska laskulajittelua käytetään välilajitteluna radix-lajittelussa.
Kuinka Radix-lajittelu toimii?
- Etsi matriisin suurin elementti, eli max. Antaa
Xolla numeroiden lukumäärämax.Xlasketaan, koska meidän täytyy käydä läpi kaikkien elementtien kaikki merkittävät paikat.
Tässä taulukossa(121, 432, 564, 23, 1, 45, 788)meillä on suurin määrä 788. Siinä on 3 numeroa. Siksi silmukan tulisi nousta satoihin paikkoihin (3 kertaa). - Käy nyt läpi kaikki merkittävät paikat yksitellen.
Käytä mitä tahansa vakaata lajittelutekniikkaa lajitellaksesi numerot jokaisessa merkittävässä paikassa. Olemme käyttäneet tähän laskutoimitusta.
Lajittele elementit yksikön paikan numeroiden (X=0) perusteella.
Laskulajittelun avulla voit lajitella elementit yksikköpaikan perusteella - Lajittele nyt elementit numeroiden perusteella kymmenissä paikoissa.
Lajittele elementit kymmenien sijainnin perusteella - Lajittele lopuksi elementit numeroiden perusteella satoihin paikkoihin.
Lajittele elementit satojen paikkojen perusteella
Radix-lajittelualgoritmi
radixSort (matriisi) d <- suurimman elementin numeroiden enimmäismäärä luo d ämpäriä, joiden koko on 0-9 i <- 0: lle, jotta d lajitellaan elementit i: n paikan numeroiden mukaan käyttäen countingSort countingSort (matriisi, d) max <- etsi suurin elementti d: n sijaelementtien joukossa alustaa laskentataulukon kaikilla nollilla j <- 0 koon mukaan etsi kunkin yksilöllisen numeron kokonaismäärä alkioiden d: nnessä paikassa ja tallenna määrä j: n indeksissä laskuryhmässä i <- 1 - max -hakuun kumulatiivinen summa ja tallenna se itse laskentaryhmään j <- koko alas 1: een palauttamaan elementit taulukon pienennyslaskelmaksi jokaisella palautetulla elementillä 1
Python-, Java- ja C / C ++ -esimerkkejä
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); )
Monimutkaisuus
Koska radix-lajittelu on ei-vertaileva algoritmi, sillä on etuja verrattuna vertailevaan lajittelualgoritmiin.
Radiksilajittelulle, joka käyttää laskulajittelua vakaana välilajitteluna, ajan monimutkaisuus on O(d(n+k)).
Tässä don O(n+k)lukusykli ja laskennan lajittelun aikakompleksi.
Siten radix-lajittelulla on lineaarinen aikakompleksuus, joka on parempi kuin O(nlog n)vertailevilla lajittelualgoritmeilla.
Jos otamme erittäin suuret numeroluvut tai muut emäkset, kuten 32- ja 64-bittiset numerot, se voi toimia lineaarisesti, mutta välilajittelu vie paljon tilaa.
Tämä tekee radix-lajittelutilasta tehotonta. Tästä syystä tällaista ei käytetä ohjelmistokirjastoissa.
Radix-lajittelusovellukset
Radix-lajittelu toteutetaan
- DC3-algoritmi (Kärkkäinen-Sanders-Burkhardt) samalla kun tehdään jälkijärjestelmä.
- paikkoja, joissa lukuja on suuria.
