翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

introsort : ウィキペディア英語版
introsort

Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. 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. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(''n'' log ''n'') runtime due to the heap sort. Since both algorithms it uses are comparison sorts, it too is a comparison sort.
Introsort was invented by David Musser in , in which he also introduced introselect, a hybrid selection algorithm based on quickselect (a variant of quicksort), which falls back to median of medians and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the purpose of providing generic algorithms for the C++ Standard Library which had both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.〔"(Generic Algorithms )", David Musser
==Pseudocode==
If a heapsort implementation and partitioning functions of the type discussed in the quicksort article are available, the introsort can be described succinctly as
procedure sort(A : array):
let maxdepth = ⌊log(length(A))⌋ × 2
introsort(A, maxdepth)

procedure introsort(A, maxdepth):
n ← length(A)
if n ≤ 1:
return ''// base case''
else if maxdepth = 0:
heapsort(A)
else:
p ← partition(A) ''// assume this function does pivot selection, p is the final position of the pivot''
introsort(A(), maxdepth - 1)
introsort(A(), maxdepth - 1)
The factor two in the maximum depth is arbitrary; it can be tuned for practical performance. denotes the array slice of items to .

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「introsort」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.