Abbiamo 100.000 frazioni: Prendiamo in considerazione le seguenti frazioni. p / (2 ^ q) tale che 0 < = p, q < = 10
Come puoi vedere ci sono < = 10 * 10 diverse frazioni, ma abbiamo 100.000 che dobbiamo ordinare (quindi ci sono piccoli elementi unici).
L'attività consiste nel pensare un algoritmo veloce per ordinare le frazioni.
Ti chiedo di guardare la mia proposta e mostrarmi le tue idee. (Suppongo che le frazioni siano date dalla coppia, ad esempio: p / q < ---- > (p, q) ) su input abbiamo array a
La mia idea:
for i = 1 to n do t[i] = a[i].first * 2^(10)
countsort (t)
bring results from t to a (remember about / 2^10)