Algoritmus Radix Sort

V tomto výučbe sa dozviete, ako funguje radix radix. Pracovné príklady radixového radenia nájdete aj v jazykoch C, C ++, Java a Python.

Radix sort je technika triedenia, pri ktorej sa prvky triedia tak, že sa najskôr zoskupia jednotlivé číslice rovnakej miestnej hodnoty . Potom prvky zoraďte podľa ich vzrastajúceho / klesajúceho poradia.

Predpokladajme, že máme pole 8 prvkov. Najskôr triedime prvky na základe hodnoty jednotkového miesta. Potom prvky roztriedime podľa hodnoty desiateho miesta. Tento proces pokračuje až do posledného významného miesta.

Počiatočné pole nech je (121, 432, 564, 23, 1, 45, 788). Je zoradený podľa druhu radix, ako je to znázornené na obrázku nižšie.

Pracovanie Radix Sort

Pred prečítaním tohto článku si prosím prečítajte zoradenie počítania, pretože počítanie zoradenia sa používa ako medziradenie v radix radení.

Ako funguje Radix Sort?

  1. Nájdite najväčší prvok v poli, tj max. Dovoliť Xje počet číslic v max. Xsa počíta, pretože musíme prejsť všetkými významnými miestami všetkých prvkov.
    V tomto poli (121, 432, 564, 23, 1, 45, 788)máme najväčšie číslo 788. Má 3 číslice. Preto by slučka mala ísť až na stovky miest (3-krát).
  2. Teraz prechádzajte postupne po každom významnom mieste.
    Pomocou akejkoľvek stabilnej techniky triedenia zoraďte číslice na každom významnom mieste. Použili sme na to počítanie druhov.
    Zoraďte prvky na základe jednotkových číslic ( X=0). Používanie počítania na triedenie prvkov na základe jednotkového miesta
  3. Teraz zoraďte prvky podľa číslic na desiatkach. Zoraďte prvky podľa miesta desiatok
  4. Nakoniec zoraďte prvky podľa číslic na stovkách miest. Zoraďte prvky na stovky miest

Algoritmus Radix Sort

 radixSort (pole) d <- maximálny počet číslic v najväčšom prvku vytvoriť d vedier veľkosti 0-9 pre i <- 0 až d triediť prvky podľa i-tých číslic pomocou counttingSort counttingSort (pole, d) max <- nájsť najväčší prvok medzi prvkami dth place inicializuje pole count so všetkými nulami pre j <- 0 na veľkosť vyhľadá celkový počet každej jedinečnej číslice na dth mieste prvkov a uloží počet na jthom indexe do poľa count pre i <- 1 na maximum nájsť kumulatívny súčet a uložte ho do samotného poľa count pre j <- veľkosť do 1 obnovte prvky do poľa znížte počet každého prvku obnoveného o 1

Príklady jazyka Python, Java a 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); )

Zložitosť

Pretože radix sort je nekomparatívny algoritmus, má oproti algoritmom komparatívneho triedenia výhody.

Pre radix radix, ktorý používa počítanie sort ako stredne stabilné triedenie, je časová zložitosť O(d(n+k)).

Tu dje číselný cyklus a O(n+k)časová zložitosť počítania.

Radix sort má teda lineárnu časovú zložitosť, ktorá je lepšia ako O(nlog n)u porovnávacích algoritmov triedenia.

Ak vezmeme veľmi veľké číselné čísla alebo počet ďalších báz, ako sú 32-bitové a 64-bitové čísla, potom to môže fungovať v lineárnom čase, avšak prechodné triedenie zaberá veľký priestor.

Toto robí radixový triediaci priestor neefektívnym. To je dôvod, prečo sa tento druh nepoužíva v softvérových knižniciach.

Aplikácie Radix Sort

Radix sort je implementovaný v

  • Algoritmus DC3 (Kärkkäinen-Sanders-Burkhardt) pri vytváraní príponového poľa.
  • miesta, kde sú počty vo veľkých rozsahoch.

Zaujímavé články...