Quick Trit vs Tri radix

Question

Dans un examen de codage, j'ai été posé une fois cette question:

En supposant que vous êtes seul trier des entiers dans l'ordre croissant, quel algorithme utilisez-vous lorsque vous souhaitez hiérarchiser la vitesse le plus, mais vous souhaitez également économiser de l'espace?

Les options étaient:

• LSD Radix Trier
• Fusionner Trier
• Quick Trit

Je pense que un argument peut être effectué entre LSD Radix Trier et Quicksort .

la sorte radiix fonctionnerait dans $ o (kn) $ et quicksort fonctionnerait dans $ O (n \ journal n) $ et pire des cas, $ o (n ^ 2) $

J'ai choisi Radix Trier comme réponse, mais je suis curieux de savoir ce que les autres avaient à dire.

Answer 1

Ceci dépend ... Si le nombre de numéros d'entrée est $ n $ , en supposant le modèle de calcul de mot-RAM, une taille de mot de $ \ theta (\ journal n) $ bits et pires entrées:

• Radix Trier nécessiterait $ O (n \ journal n) $ TIME et $ O (n) $ espace auxiliaire.

• Quicksort avec une sélection de pivot fixe ou aléatoire nécessiterait $ o (n ^ 2) $ le pire de temps et $ O (\ journal n) $ espace auxiliaire.

• fusort nécessite $ o (n \ journal n) $ temps et $ o (n) $ < / span> espace auxiliaire.

Tri radix et Sort Fusion sont alors équivalents dans ce réglage.

Notez que l'utilisation de QuicksTort avec une sélection de pivoit aléatoire entraîne une complexité de temps de $ o (n \ journal n) $ avec une probabilité élevée. Sélection du pivot de manière déterministe d'une manière qui partitionne les éléments en deux ensembles dont les cardinalités sont au plus un facteur constant donne à votre algorithme avec une complexité du temps pire des cas de $ O (n \ log n) $ et $ o (\ journal n) $ espace auxiliaire.