Pourquoi l'introsort utilise-t-il l'oreille plutôt que le mergesort?

Dans le cadre d'une affectation de devoirs couvrant la mise en œuvre de l' introsort, on me demande pourquoi le heapsort est utilisé plutôt que le mergesort (ou d'autres algorithmes d'ailleurs). $O(n\log(n))$

Introsort est un algorithme de tri hybride qui fournit à la fois des performances moyennes rapides et (asymptotiquement) des performances optimales dans le pire des cas. Il commence par tri rapide et passe à tri par tas lorsque la profondeur de récursivité dépasse un niveau basé sur (le logarithme de) le nombre d'éléments triés. ( Wikipedia , récupéré le 2014-mai-06.)

La seule raison pour laquelle je peux penser, c'est que l'oreillette est "en place" ... Mais je ne comprends pas vraiment pourquoi cela importerait ici.

algorithms algorithm-analysis sorting user672009
la source

Si l'introsort fait partie de la question, vous devrez nous dire ce que c'est avant de pouvoir dire quoi que ce soit.

Louis

Bienvenue en informatique ! Notez que vous pouvez utiliser LaTeX ici pour composer les mathématiques d'une manière plus lisible. Voir ici pour une courte introduction.

FrankW

On nous demande simplement de créer un pseudo-code pour le tri des intros et plus tard, on nous demande pourquoi il utilise heapsort plutôt que mergesort.

user672009

@ user672009 Dans ce cas, notez le code de l'un ou l'autre et voyez ce que vous trouvez. La raison peut ou non être liée à la performance.

Raphael

J'ai conclu que, depuis le tri rapide en place, nous devons utiliser un autre algorithme de tri sur place. Cependant, je suis ouvert aux commentaires.

user672009

Réponses:

Les 2 inconvénients du tri rapide sont qu'il nécessite un espace supplémentaire (pour conserver les intervalles non triés) et une mauvaise sélection de pivot (ou des séquences artificielles conçues pour vous faire sélectionner un mauvais pivot) peut en faire un temps et algorithme d'espace supplémentaire. $O(\log n)$ $O(n^2)$ $O(n)$

Le passage à heapsort lorsque la profondeur de récursivité devient trop grande (autour de ) signifie que nous avons une limite supérieure garantie qui est temps et espace supplémentaire. $\log n$ $O(n \log n )$ $O( \log n)$

$O(1)$ $O(n)$ $n$

La raison pour laquelle heapsort n'est pas utilisé pour le tri complet est parce qu'il est plus lent que quicksort (en partie à cause des constantes cachées dans l'expression big O et en partie au comportement du cache)

monstre à cliquet
la source

Mais le heapsort est utilisé ... et je soupçonne que c'est parce qu'il est en place comme quicksort.

user672009

Je soupçonne que @ user672009 est confus par votre dernière phrase. Je suggérerais de préciser que l'introsort ne commence pas par l'oreille car elle est plus lente.

Wandering Logic

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

De plus, le heapsort a beaucoup plus de ratés de cache que l'introsort.

noɥʇʎԀʎzɐɹƆ

Une bonne implémentation Quicksort n'a pas besoin d'espace O (n) dans le pire des cas, tant qu'elle se souvient du plus grand sous-intervalle sur la pile et gère immédiatement le plus petit.

gnasher729