Introsort

Introsort

Introsort ou introspective sort est un algorithme de tri par comparaisons. C'est une variante du tri rapide inventée par David Musser en 1997. Par rapport au tri rapide, Introsort a l'avantage d'avoir une complexité O(nlogn) dans le pire cas.

Principe

L'algorithme de tri rapide est ralenti lorsque le pivot choisi se retrouve souvent au début ou à la fin du sous-tableau trié. Dans ce cas, la profondeur de récursion est en O(n) et le temps total en O(n2), ce qui est un temps comparable à un tri par sélection. Mais en moyenne, le tri rapide est efficace : sa complexité est O(nlog n).

Introsort, pour pallier cet inconvénient, utilise un compteur de récursion. Ainsi il mesure au fur et à mesure la profondeur de récursion en cours (d'où le nom de l'algorithme). Quand la profondeur dépasse Klog n où K est une constante, on trie le sous-tableau restant avec un algorithme dont la complexité est O(nlog n) dans tous les cas, par exemple un tri par tas ou un Smoothsort.

Tout comme le tri rapide, Introsort peut être optimisé en triant les sous-listes de moins de 15 éléments avec un tri par insertion ou un tri de Shell, au fur et à mesure, ou à la fin (principe de Sedgesort).

Algorithme

Avec A: Tableau et n = Longueur(A)

Faire Introsort(A, 2*PartieEntière(Log2(n)) )

  • Procédure Introsort (A : Tableau[Min..Max], ProfondeurLimite : Entier > 0)
    • Initialiser
      • CurMin := Min et CurMax := Max
      • Pivot := A[PartieEntière(Min + Max / 2)]
    • Répéter jusqu'à ce que CurMin > CurMax
      • Tant que A[CurMin] < Pivot, CurMin := CurMin + 1
      • Tant que A[CurMax] > Pivot, CurMax := CurMax - 1
      • Si CurMin < CurMax alors Echanger(A[CurMin], A[CurMax])
      • CurMin = CurMin + 1
      • CurMax = CurMax - 1
    • Si CurMax > Min
      • Si ProfondeurLimite = 1 alors faire Heapsort(A[Min..CurMax])
      • Sinon faire Introsort(A[Min..CurMax], ProfondeurLimite - 1)
    • Si CurMin < Max
      • Si ProfondeurLimite = 1 alors faire Heapsort(A[CurMin..Max])
      • Sinon faire Introsort(A[CurMin..Max], ProfondeurLimite - 1)

Voir aussi

v · Algorithmes de tri

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Introsort de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Introsort — ist ein Sortieralgorithmus. Der Begriff ist eine Kurzform für „introspektives Sortieren“. Der Algorithmus ist eine Variation von Quicksort, welche in entarteten Fällen auf ein anderes Sortierverfahren mit Worst Case Laufzeit (zum Beispiel… …   Deutsch Wikipedia

  • Introsort — or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. It is the… …   Wikipedia

  • Introsort — или интроспективная сортировка  алгоритм сортировки, предложенный Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный… …   Википедия

  • Quick-Sort — Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen das Pivotelement im jeweiligen Rekursionsschritt. Quicksort (von engl. quick – schnell, to sort – sortieren) ist ein schneller, rekursiver, nicht… …   Deutsch Wikipedia

  • Quick sort — Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen das Pivotelement im jeweiligen Rekursionsschritt. Quicksort (von engl. quick – schnell, to sort – sortieren) ist ein schneller, rekursiver, nicht… …   Deutsch Wikipedia

  • Tri rapide — Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961[1] et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes.… …   Wikipédia en Français

  • Quicksort — Infobox Algorithm class=Sorting algorithm Quicksort in action on a list of numbers. The horizontal lines are pivot values. data=Varies time=O(nlog n) on average space=Varies by implementation optimal=Sometimes Stability= [Sorting… …   Wikipedia

  • Haldensortierung — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap-Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”