Un tableau de longueur N peut contenir des valeurs 1,2,3 ... N ^ 2. Est-il possible de trier en O (n)?

Question

Étant donné un tableau de longueur N. Il peut contenir des valeurs allant de 1 à partir de N ^ 2 (N carré) inclusivement, les valeurs sont solidaires. Est-il possible de trier ce tableau en O (n)? Si possible comment?

Edit:. Ce n'est pas un devoir

Answer 1

Ecrire chaque nombre entier dans la base N, qui est chaque X peut être représenté par (x1, x2) avec x = 1 + x1 + x2 * N. Maintenant, vous pouvez trier deux fois avec le comptage sorte, une fois sur x1 et x2 une fois, ce qui dans le tableau trié.

Answer 2

Oui, vous pouvez, en utilisant avec radix sorte N seaux et deux passes. Fondamentalement, vous traitez les chiffres comme ayant 2 chiffres dans la base N .

Answer 3

Il est possible de trier tout tableau d'entiers avec une valeur maximale bien définie dans le temps de O(n) en utilisant un radix sorte . Ceci est probablement le cas pour une liste d'entiers que vous rencontrez. Par exemple, si vous triez une liste d'entiers de précision arbitraire, il ne serait pas vrai. Mais tous les types C intégrales ont des plages fixes bien définies.