Den här artikeln presenterar dig Radix Sort och berättar hur du implementerar Radix Sort i C. Följande tips kommer att behandlas i den här artikeln,
Så låt oss komma igång då,
Med enkla ord betyder sortering att ordna de givna elementen i en systematisk ordning. Sortering görs i de flesta algoritmer eftersom det gör sökningen enklare vilket så småningom gör algoritmen effektiv. I den här bloggen kommer vi att förstå en av de vanliga soringalgoritmerna, dvs Radix-sortering.
Radix-sortering är en icke-jämförande algoritm för helsortering. Den sorterar siffror för siffror från den minst signifikanta siffran (dvs. siffran finns till höger) till den viktigaste siffran (den siffran finns till vänster). Radix-sortering använder räknesortering som en underrutin för att sortera.
Den nedre gränsen för jämförelsebaserad sorteringsalgoritm (som Heap sort, Quick Sort, Merge Sort) är & Omega (nLogn), och de kan inte förbättras utöver nLogn. Om vi talar om att räkna sortering är det en linjär tidssorteringsalgoritm med O (n + k) tidskomplexitet, där intervallet ligger mellan 1 och k. Nu är problemet med att räkna sorterar att det tar O (n2) när elementen sträcker sig från 1 till n2.
Så, för att sortera en matris med element som sträcker sig från 1 till n2 i linjär tid, behöver vi radiksortering. Radix sorterar sorteringsarrangemanget siffror för siffror med början från minst signifikant siffra till mest signifikant siffra. Radix-sortering använder räknesortering som en underrutin för att sortera.
Gå vidare med den här artikeln om Radix Sort Program In C,
Radix sorteringsalgoritm
Utför följande steg för alla siffror som börjar från den minst signifikanta siffran som finns i höger och rör dig mot den viktigaste siffran som finns i vänster.
Sortera elementen med hjälp av räknar sortera efter aktuell siffra.
Exempel:
hur man använder logger i java
Originalmatris:
140, 65, 85, 110, 612, 54, 12, 86
Att sortera den minst signifikanta siffran, dvs. på en plats, ger
140, 110, 612, 12, 54, 65, 85, 86
OBS: Eftersom 612 visas före 12, och sorteringen görs endast för en siffra, så visas 612 före 12 efter denna iteration.
Sortering efter nästa siffra, dvs på 10-talet, ger:
110, 612, 12, 140, 54, 65, 85, 86
Sortering efter den mest betydande siffran, dvs. närvarande på 100-talet, ger:
012, 054, 065, 085, 086, 110, 140, 612
Gå vidare med den här artikeln om Radix Sort Program In C,
Radix sorteringsprogram i C
Titta först på Radix sorteringsfunktion
Radix sorteringsfunktion:
void radixsort (int array [], int n) {// Få det största antalet för att veta det maximala antalet siffror int m = getMax (array, n) int dig // Räkningssortering utförs för varje siffra för (dig = 1 m / dig> 0 dig * = 10) countSort (array, n, dig)}Gå vidare med den här artikeln om Radix Sort Program In C,
Räkna sorteringsfunktion:
void countSort (int array [], int n, int dig) {int output [n] int i, count [10] = {0} // Lagra antalet händelser i count [] för (i = 0 i= 0 i--) {output [count [(array [i] / dig)% 10] - 1] = array [i] count [(array [i] / dig)% 10] -} // Kopiera utmatningsmatris till arr [], så att arr [] nu // innehåller sorterade nummer enligt aktuell siffra för (i = 0 iLåt oss skriva ett C-program för att implementera Radix-sortering.
Exempel:
#include // Funktion för att hitta det största numret int getMax (int array [], int n) {int max = array [0] int i för (i = 1 i max) max = array [i] return max} // Funktion för Count sort void countSort (int array [], int n, int dig) {int output [n] int i, count [10] = {0} // Lagra antalet händelser i count [] för (i = 0 i= 0 i--) {output [count [(array [i] / dig)% 10] - 1] = array [i] count [(array [i] / dig)% 10] -} // Kopiera utmatningsmatris till arr [], så att arr [] nu // innehåller sorterade nummer enligt aktuell siffra för (i = 0 i 0 dig * = 10) countSort (array, n, dig)} // Funktion att skriva ut Array void skriv ut (int arr [], int n) {int i för (i = 0 i Produktion
Efter att ha kört ovanstående program skulle du ha förstått Radix Sorteringsprogram i C. Således har vi kommit till slutet av den här artikeln om ”Quicksort i Java”. Om du vill veta mer, kolla in , ett pålitligt online-lärande företag. Edurekas Java J2EE- och SOA-utbildning och certifieringskurs är utformad för att träna dig för både grundläggande och avancerade Java-koncept tillsammans med olika Java-ramverk som Hibernate & Spring.
Har du en fråga till oss? Vänligen nämna det i kommentarsektionen på den här bloggen så kommer vi tillbaka till dig så snart som möjligt.
vad är den bästa java ideen