Ordenació eficient d'una cua X53086


Statement
 

pdf   zip   main.cc

html

Feu un procediment

template <typename T> void ordena(queue<T> &c);

que ordeni c de petit a gran utilitzant un algorisme d’ordenació eficient (amb un cost menor que quadràtic). El tipus T admet una relació d’ordre total, és a dir, tenim una operació de comparació < entre valors de tipus T.

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

Es demana que la solució només treballi amb cues. Per tant no es permet treballar amb altres estructures seqüèncials com vectors o llistes.

En els següents exemples, l’entrada consisteix en vàries línies cadascuna d’elles representant una cua: El nombre d’elements de la cua seguit dels seus valors. La sortida mostra els elements de cadascuna de les cues un cop ordenades.

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

    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
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++