Tento článok vás zoznámi s Radix Sort a povie vám, ako implementovať Radix Sort v C. Tento článok sa bude zaoberať nasledujúcimi ukazovateľmi,
Poďme teda do toho,
Jednoduchými slovami, triedenie znamená usporiadanie daných prvkov v systematickom poradí. Zoradenie sa vykonáva vo väčšine algoritmov, pretože uľahčuje vyhľadávanie, čo nakoniec zvyšuje efektívnosť algoritmu. V tomto blogu pochopíme jeden z bežne používaných soringových algoritmov, t.j. Radixovo triedenie.
Radix sort je nekomparatívny celočíselný algoritmus triedenia. Robí triedenie podľa číslic od počiatku najmenej významnej číslice (tj. Číslice vpravo) po najvýznamnejšiu číslicu (t.j. číslice vľavo). Radix sort používa počítanie sort ako podprogram na triedenie.
Dolná hranica pre porovnávací algoritmus založený na porovnávaní (napríklad Heap sort, Quick Sort, Merge Sort) je & Omega (nLogn), a preto ich nemožno vylepšiť iba za nLogn. Pokiaľ hovoríme o počítaní, je to algoritmus lineárneho triedenia času s časovou zložitosťou O (n + k), kde rozsah leží medzi 1 až k. Teraz je problém s počítaním triedenia, to trvá O (n2), keď sú prvky v rozmedzí od 1 do n2.
Aby sme mohli zoradiť pole s prvkami, ktoré sa pohybujú od 1 do n2 v lineárnom čase, potrebujeme radix radenie. Radix sort triedi číslicu poľa od číslice od najmenej významnej číslice po najvýznamnejšiu číslicu. Radix sort používa počítanie sort ako podprogram na triedenie.
Ďalej v tomto článku o programe Radix Sort In C,
Algoritmus Radix Sort
Vykonajte nasledujúce kroky pre všetky číslice, počnúc od najmenej významnej číslice vpravo, smerom k najvýznamnejšej číslici vľavo.
Zoraďte prvky pomocou počítania podľa aktuálnej číslice.
Príklad:
Originálne pole:
140, 65, 85, 110, 612, 54, 12, 86
Triedenie najmenej významnej číslice, to znamená na jednom mieste, dáva
140, 110, 612, 12, 54, 65, 85, 86
POZNÁMKA: Pretože 612 sa objaví pred 12, a triedenie sa vykonáva iba pre jednu číslicu, tak sa 612 objaví pred 12 po tejto iterácii.
Triedenie podľa ďalšej číslice, tj. Na 10. mieste, dáva:
110, 612, 12, 140, 54, 65, 85, 86
Triedenie podľa najvýznamnejších číslic, t. J. Prítomných na 100. mieste, poskytuje:
012, 054, 065, 085, 086, 110, 140, 612
Ďalej v tomto článku o programe Radix Sort In C,
Program radix Radix v C
Prvý pohľad na funkciu Radix sort
Funkcia Radix Sort:
void radixsort (int array [], int n) {// Získať čo najväčší počet, aby ste zistili maximálny počet číslic int m = getMax (pole, n) int dig // Triedenie počítania sa vykonáva pre každú číslicu pre (dig = 1 m / dig> 0 dig * = 10) countSort (pole, n, dig)}Ďalej v tomto článku o programe Radix Sort In C,
Funkcia zoradenia počtu:
void countSort (int array [], int n, int dig) {int output [n] int i, count [10] = {0} // Uložiť počet výskytov v count [] pre (i = 0 i= 0 i--) {output [count [(array [i] / dig)% 10] - 1] = array [i] count [(array [i] / dig)% 10] -} // Skopírujte výstupné pole na arr [], takže arr [] teraz // obsahuje zoradené čísla podľa aktuálnej číslice pre (i = 0 iS pokrokom napíšeme program C na implementáciu Radixovho triedenia.
Príklad:
#include // Funkcia na vyhľadanie najväčšieho čísla int getMax (int pole [], int n) {int max = pole [0] int i pre (i = 1 i max) max = pole [i] návrat max} // Funkcia pre Count sort void countSort (int pole [], int n, int dig) {int výstup [n] int i, count [10] = {0} // Uložiť počet výskytov v count [] pre (i = 0 i= 0 i--) {output [count [(array [i] / dig)% 10] - 1] = array [i] count [(array [i] / dig)% 10] -} // Skopírujte výstupné pole na arr [], takže arr [] teraz // obsahuje zoradené čísla podľa aktuálnej číslice pre (i = 0 i 0 dig * = 10) countSort (pole, n, dig)} // funkcia na vytlačenie poľa neplatné print (int arr [], int n) {int i for (i = 0 i Výkon
Teraz po vykonaní vyššie uvedeného programu by ste pochopili Radix Sort Program in C. Dostali sme sa teda na koniec tohto článku o „Quicksort v Jave“. Ak sa chcete dozvedieť viac, pozrite si , dôveryhodná online vzdelávacia spoločnosť. Výcvikový a certifikačný kurz Edureka Java J2EE a SOA je navrhnutý tak, aby vás vyškolil pre základné aj pokročilé koncepty Java spolu s rôznymi rámcami Java, ako je Hibernate & Spring.
Máte na nás otázku? Uveďte to prosím v sekcii komentárov tohto blogu a my sa vám ozveme čo najskôr.
C ++ algoritmus zlučovania