Ordenació RadixSort de naturals X94050


Statement
 

pdf   zip   main.cc

html

Fes un procediment

void ordena(vector<nat>& v);

que ordeni v de petit a gran utilitzant l’algorisme d’ordenació RadixSort.

Només s’ha d’enviar el procediment requerit.

Es demana que la solució utilitzi l’algorisme RadixSort descomposant els naturals en els seus bits. El nombre de bits que conté un natural és:

num_bits = sizeof(nat) * 8

i el bit de la posició r d’un natural n es pot obtenir així:

(n & ( 1 << r )) >> r

sent r ∈ [0, num_bits−1]

En els següents exemples, l’entrada consisteix en vàries línies cadascuna d’elles representant un vector: El nombre d’elements del vector seguit dels seus valors. La sortida mostra els elements de cada vector un cop ordenats.

Public test cases

  • Input

    1 10
0
2 10 20
2 20 10
3 10 20 30
3 10 30 20
3 20 30 10
3 20 10 30
3 30 10 20
3 30 20 10
4 1 2 3 4
4 1 2 4 3 
4 1 3 2 4
4 1 3 4 2 
4 1 4 2 3
4 1 4 3 2 
4 4 2 3 1
4 4 2 1 3 
4 4 3 2 1
4 4 3 1 2 
4 4 1 2 3
4 4 1 3 2
6 4 1 3 2 1 4
6 4 1 3 2 3 3

    Output

    10 

10 20 
10 20 
10 20 30 
10 20 30 
10 20 30 
10 20 30 
10 20 30 
10 20 30 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 1 2 3 4 4 
1 2 3 3 3 4

  • Input

    12 294967294 294367294 284967294 4995 992 774 1878 4962 1070 21 123456789 987654321

    Output

    21 774 992 1070 1878 4962 4995 123456789 284967294 294367294 294967294 987654321
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++