algorithm
Radix Sort

Radix Sort Basic Information

Radix Sort är en lägre bunden jämförelse baserad algoritm. Det är en icke-jämförande heltalssorteringsalgoritm som sorterar data med heltalstangenter genom att gruppera nycklar efter individuella siffror som delar någon betydande position och värde. Radix sortering är en linjär tidssorteringsalgoritm som sorterar i O (n + k) tid när element är inom området från 1 till k. Idén med Radix Sort är att göra siffror för siffror sortera från minst betydande siffror till mest betydelsefulla siffror. Radix sortering använder räknasortering som en subroutin för att sortera. Radix sortering är generalisering av hinkens sortering.

Pseudokod för hinksortering:

1. Skapa en grupp med [0..n-1] -element.
2. Call Bucket Sortera upprepade gånger på minst till den viktigaste siffran i varje element som nyckel.
3. Returnera den sorterade matrisen.

Exempel på Radix Sort:

Space Auxiliary: O(n)
Tidskomplexitet: O(n)