Algoritmus Radix Sort

Obsah

Jak funguje Radix Sort?
Algoritmus Radix Sort
Python, Java a C / C ++ příklady
Složitost
Radix Sort Applications

V tomto kurzu se naučíte, jak funguje radix sort. Také najdete pracovní příklady řazení radixů v C, C ++, Java a Python.

Radix sort je technika třídění, která třídí prvky tak, že nejprve seskupíte jednotlivé číslice stejné hodnoty místa . Poté seřaďte prvky podle jejich vzestupného / sestupného pořadí.

Předpokládejme, že máme řadu 8 prvků. Nejprve roztřídíme prvky na základě hodnoty jednotkového místa. Potom roztřídíme prvky podle hodnoty desátého místa. Tento proces pokračuje až do posledního významného místa.

Nechť je počáteční pole (121, 432, 564, 23, 1, 45, 788). Je tříděno podle druhu radix, jak je znázorněno na obrázku níže.

Práce Radix Sort

Před přečtením tohoto článku si projděte třídění počítání, protože počítání třídění se používá jako střední třídění v radix řazení.

Jak funguje Radix Sort?

Najděte největší prvek v poli, tj. Max. Dovolit Xje počet číslic max. Xse počítá, protože musíme projít všemi významnými místy všech prvků.
V tomto poli (121, 432, 564, 23, 1, 45, 788)máme největší číslo 788. Má 3 číslice. Proto by smyčka měla jít až na stovky míst (třikrát).
Nyní projděte postupně každé významné místo.
K třídění číslic na každém významném místě použijte jakoukoli stabilní techniku třídění. K tomu jsme použili počítání.
Řadit prvky na základě číslic jednotky ( X=0). Použití počítání třídění k třídění prvků na základě jednotkového místa
Nyní seřaďte prvky podle číslic na místě desítek. Řazení prvků na základě desítek míst
Nakonec seřaďte prvky podle číslic na stovkách. Řazení prvků na základě stovek míst

Algoritmus Radix Sort

 radixSort (pole) d <- maximální počet číslic v největším prvku vytvořit d kbelíky o velikosti 0-9 pro i <- 0 až d seřadit prvky podle ith místo číslic pomocí counttingSort counttingSort (pole, d) max <- najít největší prvek mezi dth místo prvky inicializovat počet pole se všemi nulami pro j <- 0 na velikost najít celkový počet každé jedinečné číslice v dth místo prvků a uložit počet na jth indexu v poli počet pro i <- 1 až max najít kumulativní součet a uložit jej do samotného počtu count pro j <- velikost do 1 obnovit prvky do pole snížit počet každého prvku obnoveného o 1

Python, Java a C / C ++ příklady

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žitost

Protože radix sort je nekomparativní algoritmus, má oproti srovnávacím algoritmům řazení výhody.

U radixového řazení, které používá počítání jako střední stabilní řazení, je časová složitost O(d(n+k)).

Tady dje číselný cyklus a O(n+k)časová složitost počítání.

Takže radix sort má lineární časovou složitost, která je lepší než O(nlog n)u srovnávacích algoritmů třídění.

Vezmeme-li velmi velká číselná čísla nebo počet dalších základen, jako jsou 32bitová a 64bitová čísla, pak může fungovat v lineárním čase, avšak přechodné třídění zabírá velký prostor.

Díky tomu je radixový třídicí prostor neefektivní. To je důvod, proč se tento druh nepoužívá v softwarových knihovnách.