Ordenant paraules P50728

Donat un vector de paraules amb longituds entre 1 i 10, on cada paraula té o bé només lletres minúscules o bé només lletres majúscules, cal obtenir un nou vector amb les mateixes paraules però en aquest ordre:

• abans, les paraules amb lletres minúscules;

• en cas d’empat, les paraules més curtes;

• en cas d’un altre empat, respectant l’ordre relatiu en el vector.

Per exemple, si el vector conté [ HELLO, ivet, anna, HI, BYE, pep ], el resultat ha de ser [ pep, ivet, anna, HI, BYE, HELLO ].

Escriviu un procediment

    vector<string> ordena_sense_sort(const vector<string>& V);

que retorni un @vector<string>@ amb el resultat d’ordenar les paraules de @V@ amb els criteris indicats anteriorment.

Precondició

Totes les paraules de @V@ són diferents, i cadascuna té entre 1 i 10 lletres, que són o bé totes minúscules o bé totes majúscules.

Observació

Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

La solució esperada no usa el @sort()@ ni cap algorisme similar i té cost $O(n)$, on $n$ és la mida del vector. Amb una solució “raonable” de cost $O(n \log n)$ el jutge us donarà 70 punts, i podreu obtenir una nota màxima de 7 en aquest problema.