Timsort (original) (raw)
Timsort ist ein hybrider Sortieralgorithmus, der von Mergesort und Insertionsort abgeleitet ist. Er wurde entwickelt, um auf verschiedenen realen Daten schnell zu arbeiten. Er wurde 2002 von Tim Peters für die Nutzung in Python entwickelt und ist ab der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch in Java SE 7 und auf der Android-Plattform genutzt.
| Property | Value |
|---|---|
| dbo:abstract | Timsort ist ein hybrider Sortieralgorithmus, der von Mergesort und Insertionsort abgeleitet ist. Er wurde entwickelt, um auf verschiedenen realen Daten schnell zu arbeiten. Er wurde 2002 von Tim Peters für die Nutzung in Python entwickelt und ist ab der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch in Java SE 7 und auf der Android-Plattform genutzt. (de) Timsort est un algorithme de tri dérivé du tri fusion et du tri par insertion, stable et conçu pour fonctionner de manière efficace sur des données réelles. Il a été mis au point par Tim Peters en 2002 pour le langage de programmation Python. L'algorithme procède en cherchant des monotonies, c'est-à-dire des parties de l'entrée déjà correctement ordonnées, et peut de cette manière trier efficacement l'ensemble des données en procédant par fusions successives. Pour des entrées de petites tailles, il revient à effectuer un tri fusion. Timsort est l'algorithme standard de tri utilisé par Python depuis la version 2.3. Il est également utilisé pour trier des données de types non-primitifs en Java 7, ainsi que par Android et GNU Octave. Une variante de l'algorithme, Adaptive Shivers Sort, a été proposée par Vincent Jugé (fr) ティムソート (Timsort) は2002年にPythonで によって実装された安定ソートアルゴリズムの一種。マージソートと挿入ソートから派生しており、実世界の多くの種類のデータで適切に機能するように設計されている。 このアルゴリズムは、すでに整列されているデータのサブシーケンスを見つけ、それらを使用して残りをより効率的にソートします。これは、特定の基準が満たされるまで並びをマージすることによって行われます。 ティムソートは、バージョン2.3以降のPythonの標準的な並べ替えアルゴリズムで、Java SE 7 、Androidプラットフォーム 、GNU Octave 、V8 、Swift 、Rust においても非プリミティブ型の配列のソートアルゴリズムとして採用されています。 ティムソートは、PeterMcIlroyの1993年の論文「Optimistic Sorting and Information Theoretic Complexity」の手法を使用しています。 (ja) Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, on V8, Swift, and Rust. It uses techniques from Peter McIlroy's 1993 paper "Optimistic Sorting and Information Theoretic Complexity". (en) In informatica il Timsort è un algoritmo di ordinamento derivato dal merge sort e dall'insertion sort. La sua struttura è ottimizzata per trattare diversi tipi di dato. Il suo nome deriva da quello del suo inventore, , che lo ha creato nel 2002 quale algoritmo di ordinamento standard del linguaggio di programmazione Python e di Rust, in cui è stato integrato a partire dalla versione 2.3. È anche utilizzato per ordinare i vettori in Java 7. (it) Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В настоящее время Timsort является стандартным алгоритмом сортировки в Python, OpenJDK 7, Apple Swift Standard Library 5 и реализован в Android JDK 1.5.Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки. (ru) Timsort — гібридний стабільний алгоритм сортування, який поєднує в собі сортування злиттям та сортування включенням, призначений для ефективної роботи з багатьма видами реальних даних. Він був втілений в життя Тімом Пітерсом у 2002 році для використання у мові програмування Python. Алгоритм знаходить підпослідовності даних, які вже впорядковані, і використовує їх для більш ефективного сортування залишків. Це робиться шляхом об'єднання впорядкованих частин до виконання певних критеріїв. Timsort був стандартним алгоритмом сортування Python з версії 2.3. Він також використовується для сортування масивів не примітивного типу в Java SE 7, на платформі Android, у GNU Octave, Swift, та Rust. Він використовує прийоми з статті Пітера Макілроя 1993 року «Оптимістичне сортування та теоретична складність інформації». (uk) Timsort é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar arrays em Java SE 7. Tim Peters descreve o algoritmo da seguinte forma: [...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu mereço ). Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente sintonizado, híbrido, samplesort de Python em matrizes aleatórias.Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores "inteligentemente". Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória. Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de . De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de , no caso médio, o que exige que a ordenação por comparação tome um tempo de em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que , porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa. (pt) Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 的"乐观排序和信息理论上复杂性"中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7, Android platform, GNU Octave, 谷歌浏览器, 和 Swift 用于对非原始类型的数组排序。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Representation_of_sta...merge_memory_in_Timsort.svg?width=300 |
| dbo:wikiPageExternalLink | http://bugs.python.org/file4451/timsort.txt https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.78%3FmobileUi=0& https://hal-upec-upem.archives-ouvertes.fr/hal-01212839 https://drops.dagstuhl.de/opus/volltexte/2018/9467/ |
| dbo:wikiPageID | 23954341 (xsd:integer) |
| dbo:wikiPageLength | 18294 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117237919 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:Binary_search_algorithm dbr:Best,_worst_and_average_case dbr:V8_(JavaScript_engine) dbr:Insertion_sort dbr:Rust_(programming_language) dbr:GNU_Octave dbr:Android_(operating_system) dbr:Linear_search dbr:CPU_cache dbr:Adaptive_sort dbc:Comparison_sorts dbc:Sorting_algorithms dbr:Timsort dbr:Formal_verification dbr:Java_7 dbr:Hybrid_algorithm dbr:Array_data_structure dbr:KeY dbc:Stable_sorts dbr:Swift_(programming_language) dbr:Tim_Peters_(software_engineer) dbr:Sorting_algorithm dbr:Merge_sort dbr:Exponential_search dbr:Binary_search dbr:File:Copy_galloping_mode_timsort(2).svg dbr:File:Merging_procedure_for_timsort.svg dbr:File:One-one_merging_timsort.svg dbr:File:Representation_of_stack_for_merge_memory_in_Timsort.svg dbr:File:Selection_of_minrun_by_timsort.png |
| dbp:caption | A visual representation of Timsort (en) |
| dbp:class | dbr:Sorting_algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:optimal | Yes (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_web dbt:Mvar dbt:Ordered_list dbt:R dbt:Reflist dbt:Use_dmy_dates dbt:Val dbt:Abs dbt:Infobox_Algorithm dbt:Sorting |
| dcterms:subject | dbc:Comparison_sorts dbc:Sorting_algorithms dbc:Stable_sorts |
| rdf:type | yago:WikicatComparisonSorts yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | Timsort ist ein hybrider Sortieralgorithmus, der von Mergesort und Insertionsort abgeleitet ist. Er wurde entwickelt, um auf verschiedenen realen Daten schnell zu arbeiten. Er wurde 2002 von Tim Peters für die Nutzung in Python entwickelt und ist ab der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch in Java SE 7 und auf der Android-Plattform genutzt. (de) ティムソート (Timsort) は2002年にPythonで によって実装された安定ソートアルゴリズムの一種。マージソートと挿入ソートから派生しており、実世界の多くの種類のデータで適切に機能するように設計されている。 このアルゴリズムは、すでに整列されているデータのサブシーケンスを見つけ、それらを使用して残りをより効率的にソートします。これは、特定の基準が満たされるまで並びをマージすることによって行われます。 ティムソートは、バージョン2.3以降のPythonの標準的な並べ替えアルゴリズムで、Java SE 7 、Androidプラットフォーム 、GNU Octave 、V8 、Swift 、Rust においても非プリミティブ型の配列のソートアルゴリズムとして採用されています。 ティムソートは、PeterMcIlroyの1993年の論文「Optimistic Sorting and Information Theoretic Complexity」の手法を使用しています。 (ja) In informatica il Timsort è un algoritmo di ordinamento derivato dal merge sort e dall'insertion sort. La sua struttura è ottimizzata per trattare diversi tipi di dato. Il suo nome deriva da quello del suo inventore, , che lo ha creato nel 2002 quale algoritmo di ordinamento standard del linguaggio di programmazione Python e di Rust, in cui è stato integrato a partire dalla versione 2.3. È anche utilizzato per ordinare i vettori in Java 7. (it) Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В настоящее время Timsort является стандартным алгоритмом сортировки в Python, OpenJDK 7, Apple Swift Standard Library 5 и реализован в Android JDK 1.5.Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки. (ru) Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 的"乐观排序和信息理论上复杂性"中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7, Android platform, GNU Octave, 谷歌浏览器, 和 Swift 用于对非原始类型的数组排序。 (zh) Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, on V8, Swift, and Rust. (en) Timsort est un algorithme de tri dérivé du tri fusion et du tri par insertion, stable et conçu pour fonctionner de manière efficace sur des données réelles. Il a été mis au point par Tim Peters en 2002 pour le langage de programmation Python. L'algorithme procède en cherchant des monotonies, c'est-à-dire des parties de l'entrée déjà correctement ordonnées, et peut de cette manière trier efficacement l'ensemble des données en procédant par fusions successives. Pour des entrées de petites tailles, il revient à effectuer un tri fusion. (fr) Timsort é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar arrays em Java SE 7. Tim Peters descreve o algoritmo da seguinte forma: Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de . (pt) Timsort — гібридний стабільний алгоритм сортування, який поєднує в собі сортування злиттям та сортування включенням, призначений для ефективної роботи з багатьма видами реальних даних. Він був втілений в життя Тімом Пітерсом у 2002 році для використання у мові програмування Python. Алгоритм знаходить підпослідовності даних, які вже впорядковані, і використовує їх для більш ефективного сортування залишків. Це робиться шляхом об'єднання впорядкованих частин до виконання певних критеріїв. Timsort був стандартним алгоритмом сортування Python з версії 2.3. Він також використовується для сортування масивів не примітивного типу в Java SE 7, на платформі Android, у GNU Octave, Swift, та Rust. (uk) |
| rdfs:label | Timsort (de) Timsort (it) Timsort (fr) ティムソート (ja) 팀소트 (ko) Timsort (pt) Timsort (ru) Timsort (en) Timsort (zh) Timsort (uk) |
| owl:sameAs | freebase:Timsort yago-res:Timsort wikidata:Timsort dbpedia-de:Timsort dbpedia-fa:Timsort dbpedia-fr:Timsort dbpedia-it:Timsort dbpedia-ja:Timsort dbpedia-ko:Timsort dbpedia-pt:Timsort dbpedia-ru:Timsort dbpedia-sr:Timsort dbpedia-uk:Timsort dbpedia-zh:Timsort https://global.dbpedia.org/id/55kuj |
| prov:wasDerivedFrom | wikipedia-en:Timsort?oldid=1117237919&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Copy_galloping_mode_timsort(2).svg wiki-commons:Special:FilePath/Merging_procedure_for_timsort.svg wiki-commons:Special:FilePath/One-one_merging_timsort.svg wiki-commons:Special:FilePath/Representation_of_stack_for_merge_memory_in_Timsort.svg wiki-commons:Special:FilePath/Selection_of_minrun_by_timsort.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Timsort |
| is dbo:wikiPageRedirects of | dbr:Tim_sort |
| is dbo:wikiPageWikiLink of | dbr:Quicksort dbr:List_of_algorithms dbr:Block_sort dbr:Algorithmic_efficiency dbr:Analysis_of_algorithms dbr:Comparison_sort dbr:Bubble_sort dbr:Adaptive_sort dbr:Timsort dbr:Java_version_history dbr:Hybrid_algorithm dbr:Cocktail_shaker_sort dbr:Tim_Peters_(software_engineer) dbr:Sorting_algorithm dbr:Merge_sort dbr:Recursion_(computer_science) dbr:Tim_sort |
| is foaf:primaryTopic of | wikipedia-en:Timsort |
