| dbo:abstract
|
- Introsort nebo také introspektivní třídění, je jedna z možných metod vnitřního třídění. Tuto metodu popsal v roce 1997 David Musser. Introsort se opírá o tzv. algoritmy rychlého řazení a řazení haldou a vhodně je kombinuje. Výhodou je, že se snaží zamezit případům, kdy je složitost rychlého řazení úměrná O(n2), tj. když při dělicí funkci dělíme v každém kroku tak, že tříděnou množinu prvků {a1,a2, …, an} rozdělíme tak, že v jedné podmnožině bude jeden prvek, a v druhé n-1 prvků. (cs)
- 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 Heapsort) zurückfällt.Dazu wird zu Beginn jedes Rekursionsschrittes anhand einer Bewertungsfunktion entschieden, ob ein anderer Algorithmus für die Sortierung der Teilliste verwendet werden soll (zum Beispiel bei Erreichen einer bestimmten Rekursionstiefe). Auf diese Weise wird die Geschwindigkeit von Quicksort mit einer worst-case Zeitkomplexität gekoppelt (gegenüber bei reinem Quicksort). Die exakte Laufzeit ist in den entarteten Fällen etwas höher als bei direkter Anwendung des optimalen Algorithmus, da bis zum Rückfall auf das alternative Sortierverfahren Quicksort durchlaufen wird. Bekannt geworden ist Introsort vor allem dadurch, dass Silicon Graphics in seiner Standard Template Library für C++ seit einigen Jahren auf Introsort statt Quicksort zurückgreift. Inzwischen wurde Introsort auch in andere Implementierungen der C++ Standard Library übernommen, unter anderem in die der GCC. (de)
- 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, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three 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 the three algorithms it uses are comparison sorts, it is also 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. Introsort is in place and not stable. (en)
- Introsort ou introspective sort est un algorithme de tri par comparaisons. C'est une variante du tri rapide inventée par en 1997. Par rapport au tri rapide, Introsort a l'avantage d'avoir une complexité dans le pire cas. (fr)
- イントロソート（英: introsort）は、 が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。 最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。 イントロソートは、クイックソートやヒープソートと同様、である。 クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n2) となる。よりロバストな方法として先頭、最後尾、中央の値の中央値をピボットに選ぶアルゴリズム（median-of-3 pivot）もある。大抵のデータ列のソートはこれでほとんどうまくいくが、データ列を工夫することで性能を大幅に低下させることができ、DoS攻撃に利用できる。 Musser は、median-of-3 pivot クイックソートが最悪値を示すようなデータであっても、例えば要素数 100000 のデータに対してイントロソートの実行時間がクイックソートの 1/200 になったことを報告している。 Musser は Robert Sedgewick が考案したキャッシュメモリの効果を考慮したソートアルゴリズムも検討した。それは、細かい部分について挿入ソートを1回最後に行うというものである。彼によると、イントロソートではキャッシュミス率は2倍になるが、両端キューを使った実装では劇的に性能を改善できるため、テンプレートライブラリに保持すべきだとしている（特に、キャッシュの保持されている間にソートを行わないこともあるため）。 クイックソートと同様の考えを適用した選択アルゴリズムとして、アントニー・ホーアのクイックセレクトがある。選択アルゴリズムも同様にイントロソートの考えを適用でき、の計算量は、最悪時間でも線形時間となる（クイックセレクトの最悪時間は O(n2)）。 2000年6月、SGI C++ Standard Template Library で、Musser のイントロソートの手法を利用した不安定ソートの実装をした。ヒープソートに切り替える再帰の深さは引数で指定でき、最終段は Sedgewick の挿入ソートを使う方式である。挿入ソートに切り替わる再帰の深さは16だった。 (ja)
- Introsort ou introspective sort é um algoritmo de ordenação criado por em 1997. Ele começa com o quicksort e muda para o heapsort quando a profundidade da recursividade excede um nível baseado no (logaritmo do) número de elementos a ser classificados. É o melhor dos dois mundos, com um tempo de execução de pior caso de O(n log n) e desempenho prático comparável ao quicksort em conjuntos de dados típicos. Uma vez que ambos os algoritmos que utiliza são ordenações de comparação, ele também é uma ordenação por comparação. Em quicksort, uma das operações críticas é a escolha do pivô: o elemento em torno do qual a lista é particionada. O algoritmo mais simples de seleção do pivô é tomar o primeiro ou o último elemento da lista como o pivô, obtendo um comportamento pobre para o caso de entradas ordenadas ou quase totalmente ordenadas. A variante de Niklaus Wirth usa o elemento do meio para prevenir essas ocorrências, degenerando em O(n²) para seqüências inventadas. O algoritmo de seleção de pivô "mediana melhor-de-três" obtém a mediana do primeiro, médio e últimos elementos da lista; no entanto, mesmo que isso funcione bem em muitos exemplos do mundo real, ainda é possível inventar uma lista matadora de mediana melhor-de-três que irá causar desaceleração dramática de um quicksort com base nesta técnica de seleção do pivô. Essas contribuições poderiam potencialmente ser explorada por um agressor, por exemplo, enviar essa lista para um servidor de Internet para ordenação como um ataque de negação de serviço. Musser relatou que em uma seqüência ''matadora de mediana melhor-de-três de 100.000 elementos, o tempo de excução do introsort foi de 1/200 do que o do quicksort "mediana melhor-de-três". Musser também considerou o efeito sobre o da pequena ordenação atrasada de , onde pequenos intervalos são classificados no final, em uma única passagem do insertion sort. Ele relatou que seria possível dobrar o número de erros de cache, mas que o seu desempenho com deques foi significativamente melhor e deve ser mantido para modelos de bibliotecas, em parte porque o ganho em outros casos, de fazer as ordenações imediatamente não foi grande. Da mesma forma, Musser também introduziu o de pior caso linear com tempo comparável ao algoritmo de Hoare, uma simples adaptação do quicksort que é o algoritmo de seleção mais eficiente utilizado na prática. Isso é chamado seleção por introspecção ou "Introselect". (pt)
- Sortowanie introspektywne (ang. introspective sort lub introsort) – odmiana sortowania hybrydowego, w której wyeliminowany został problem złożoności O(n2) występującej w najgorszym przypadku algorytmu sortowania szybkiego. (pl)
- Introsort или интроспективная сортировка — алгоритм сортировки, предложенный Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Этот подход сочетает в себе достоинства обоих методов с худшим случаем O(n log n) и быстродействием, сравнимым с быстрой сортировкой. Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений. В быстрой сортировке одна из критичных операций — выбор опоры (элемент, относительно которого разбивается массив). Простейший алгоритм выбора основы — взятие первого или последнего элемента массива за опору чревато плохим поведением на отсортированных или почти отсортированных данных. Никлаус Вирт предложил использовать серединный элемент для предотвращения этого случая, деградирующего до O(n²) при неудачных входных данных. Алгоритм выбора опоры «медиана трёх» выбирает опорой средний из первого, среднего и последнего элементов массива. Однако, несмотря на то, что он работает хорошо на большинстве входных данных, все же возможно найти такие входные данные, которые сильно замедлят этот алгоритм сортировки. Такие данные потенциально могут использоваться злоумышленниками. Например, злоумышленники могут посылать такой массив Веб-серверу, добиваясь отказа в обслуживании. Мюссер выяснил, что на худшем наборе данных для алгоритма быстрой сортировки «медиана из трёх» (рассматривался массив из 100 тысяч элементов) introsort работает примерно в 200 раз быстрее. Он также оценил эффект от кеша в случае сортировки Роберта Седжвика, когда небольшие диапазоны сортируются в конце одиночным проходом сортировки вставками. Он выяснил, что такой подход может удвоить количество промахов кеша, но его производительность при использовании двухсторонней очереди значительно лучше, и его следует оставить для библиотек шаблонов, отчасти потому, что выигрыш в других случаях не велик. В реализации Стандартной библиотеки шаблонов C++ от SGI (stl_algo.h) для неустойчивой сортировки используется подход Мюссера с контролем глубины рекурсии, для переключения на алгоритм пирамидальной сортировки, выбор неподвижного элемента как медианы из трёх и в конце применяется алгоритм сортировки вставками Кнута для последовательностей, содержащих менее чем 16 элементов. (ru)
- 内省排序（英語：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。 在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点选择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。Niklaus Wirth为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特定序列上性能退化为的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素取得中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DoS）攻击的潜在可能性。 Musser研究指出，在针对3基准中位数选择算法设计的100,000个元素的“破解序列”上，内省排序的运行时间是这种3基准快速排序的1 / 200。在Musser的算法中，最终较小范围内数据的排序由Sedgewick提出的小数据排序算法完成。 在2000年6月，SGI的C++标准模板库的stl_algo.h （页面存档备份，存于互联网档案馆）中的不稳定排序算法采用了Musser的内省排序算法。在此实现中，切换到插入排序的数据量阈值为16个。 (zh)
|
| rdfs:comment
|
- Introsort nebo také introspektivní třídění, je jedna z možných metod vnitřního třídění. Tuto metodu popsal v roce 1997 David Musser. Introsort se opírá o tzv. algoritmy rychlého řazení a řazení haldou a vhodně je kombinuje. Výhodou je, že se snaží zamezit případům, kdy je složitost rychlého řazení úměrná O(n2), tj. když při dělicí funkci dělíme v každém kroku tak, že tříděnou množinu prvků {a1,a2, …, an} rozdělíme tak, že v jedné podmnožině bude jeden prvek, a v druhé n-1 prvků. (cs)
- Introsort ou introspective sort est un algorithme de tri par comparaisons. C'est une variante du tri rapide inventée par en 1997. Par rapport au tri rapide, Introsort a l'avantage d'avoir une complexité dans le pire cas. (fr)
- Sortowanie introspektywne (ang. introspective sort lub introsort) – odmiana sortowania hybrydowego, w której wyeliminowany został problem złożoności O(n2) występującej w najgorszym przypadku algorytmu sortowania szybkiego. (pl)
- 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 Heapsort) zurückfällt.Dazu wird zu Beginn jedes Rekursionsschrittes anhand einer Bewertungsfunktion entschieden, ob ein anderer Algorithmus für die Sortierung der Teilliste verwendet werden soll (zum Beispiel bei Erreichen einer bestimmten Rekursionstiefe). (de)
- 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, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three 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 the three algorithms it uses are comparison sorts, it is also a comparison sort. (en)
- イントロソート（英: introsort）は、 が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。 最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。 イントロソートは、クイックソートやヒープソートと同様、である。 クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n2) となる。よりロバストな方法として先頭、最後尾、中央の値の中央値をピボットに選ぶアルゴリズム（median-of-3 pivot）もある。大抵のデータ列のソートはこれでほとんどうまくいくが、データ列を工夫することで性能を大幅に低下させることができ、DoS攻撃に利用できる。 (ja)
- Introsort ou introspective sort é um algoritmo de ordenação criado por em 1997. Ele começa com o quicksort e muda para o heapsort quando a profundidade da recursividade excede um nível baseado no (logaritmo do) número de elementos a ser classificados. É o melhor dos dois mundos, com um tempo de execução de pior caso de O(n log n) e desempenho prático comparável ao quicksort em conjuntos de dados típicos. Uma vez que ambos os algoritmos que utiliza são ordenações de comparação, ele também é uma ordenação por comparação. (pt)
- Introsort или интроспективная сортировка — алгоритм сортировки, предложенный Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Этот подход сочетает в себе достоинства обоих методов с худшим случаем O(n log n) и быстродействием, сравнимым с быстрой сортировкой. Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений. (ru)
- 内省排序（英語：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。 在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点选择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。Niklaus Wirth为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特定序列上性能退化为的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素取得中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DoS）攻击的潜在可能性。 Musser研究指出，在针对3基准中位数选择算法设计的100,000个元素的“破解序列”上，内省排序的运行时间是这种3基准快速排序的1 / 200。在Musser的算法中，最终较小范围内数据的排序由Sedgewick提出的小数据排序算法完成。 (zh)
|
