Smoothsort (original) (raw)
Das Smoothsort-Sortierverfahren ist eine Variation von Heapsort, welche von Edsger W. Dijkstra 1981 entwickelt wurde. Der Vorteil liegt darin, dass es im Best-Case mit einem Aufwand von bei vorsortierten Folgen auskommt. Auf Grund der Kompliziertheit wird es aber selten benutzt. Dies liegt daran, dass es im Worst-Case und Average-Case mit einer Laufzeit von keine Verbesserung gegenüber dem Heapsort-Algorithmus mitbringt.
Property | Value |
---|---|
dbo:abstract | Das Smoothsort-Sortierverfahren ist eine Variation von Heapsort, welche von Edsger W. Dijkstra 1981 entwickelt wurde. Der Vorteil liegt darin, dass es im Best-Case mit einem Aufwand von bei vorsortierten Folgen auskommt. Auf Grund der Kompliziertheit wird es aber selten benutzt. Dies liegt daran, dass es im Worst-Case und Average-Case mit einer Laufzeit von keine Verbesserung gegenüber dem Heapsort-Algorithmus mitbringt. (de) Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. C'est un tri de complexité en , tout comme le tri par tas dont il est inspiré, et le tri rapide dans la plupart des cas. Mais si les données sont déjà presque triées, il est de complexité en . Ce tri est alors plus rapide que le tri rapide. La transition entre les temps d'exécution entre les listes déjà triées et les listes mélangées ou à l'envers est progressive d'où le nom smoothsort, smooth signifiant doux, lisse. C'est un tri sur place, c'est-à-dire qu'il n'y a pas de zone mémoire allouée supplémentaire pour stocker les éléments. Si l'algorithme smoothsort est plus rapide que le tri par tas pour des listes peu mélangées, il est légèrement plus lent que le tri par tas pour des listes qui sont plutôt dans le sens décroissant au départ. En effet, les données de départ sont alors plus proche de la structure de tas. (fr) In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n), but it is not a stable sort. The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state. (en) In informatica lo Smoothsort (metodo) è un algoritmo di ordinamento particolarmente indicato per ordinare liste di dati già parzialmente ordinate. Lo Smoothsort è una variante dell'Heap sort sviluppata da Edsger Dijkstra nel 1981: come l'Heap sort anche lo Smoothsort presenta il limite computazionale massimo pari a O(n log n). Lo Smoothsort, però, si avvicina ad un tempo O(n) se i dati in ingresso sono già parzialmente ordinati, mentre l'Heap sort mediamente impiega O(n log n), indifferentemente dal livello di ordinamento iniziale. (it) Плавне сортування (англ. Smoothsort) — алгоритм сортування, різновид пірамідального сортування, розроблений Е. Дейкстрою 1981 року. Як і пірамідальне сортування, в найгіршому випадку має швидкодію О(n log n). Перевагою плавного сортування є те, що його швидкодія наближається до O(n), якщо вхідні дані частково відсортовано, в той час як швидкодія пірамідального сортування є незмінною та не залежить від стану вхідних даних. (uk) Algoritmo de ordenação relativamente simples. É um algoritmo de ordenação por comparação Smoothsort (método) é um algoritmo de ordenação de ordenação por comparação. É uma variação do heapsort e foi desenvolvido por Edsger Dijkstra em 1981. Como o heapsort, o limite superior do smoothsort é de O(n log n). A vantagem de smoothsort é que ele se aproxima de tempo O(n) se a entrada já tem algum grau de ordenação, enquanto a média do heapsort é de O(n log n), independentemente do estado inicial em termos de ordenação. (pt) Плавная сортировка (англ. Smoothsort) — алгоритм сортировки выбором, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную O(n log n). Преимущество плавной сортировки в том, что её сложность приближается к O(n), если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных. (ru) |
dbo:thumbnail | wiki-commons:Special:FilePath/Smoothsort.gif?width=300 |
dbo:wikiPageExternalLink | https://www.enterag.ch/hartwig/order/smoothsort.pdf https://www.keithschwarz.com/smoothsort/ http://hdl.handle.net/2433/98975 https://github.com/Morwenn/poplar-heap |
dbo:wikiPageID | 100450 (xsd:integer) |
dbo:wikiPageLength | 17748 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1098544685 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Binary_heap dbr:Binary_tree dbr:Golden_ratio dbr:Musl dbr:Transdichotomous_machine_model dbr:Stable_sort dbr:Comparison_sort dbr:Computer_science dbr:Leonardo_number dbr:Polder dbr:Priority_queue dbr:Adaptive_sort dbc:Comparison_sorts dbc:Sorting_algorithms dbr:Tree_traversal dbr:Heap_(data_structure) dbr:Amortized_analysis dbc:Heaps_(data_structures) dbr:Fibonacci_number dbc:Edsger_W._Dijkstra dbr:Heapsort dbr:Array_data_structure dbr:Asymptotic_analysis dbr:Big_O_notation dbr:Binomial_heap dbr:Sorting_algorithm dbr:In-place_algorithm dbr:Implicit_data_structure dbr:Edsger_Dijkstra dbr:Bit_vector dbr:File:Smoothsort.gif dbr:Wikibooks:Algorithm_Implementation/Sorting/Smoothsort dbr:Wikt:trinkle |
dbp:caption | Smoothsort operating on an array which is mostly in order. The bars across the top show the tree structure. (en) |
dbp:class | dbr:Sorting_algorithm |
dbp:data | dbr:Array_data_structure |
dbp:optimal | When the data is already sorted (en) |
dbp:space | total, auxiliary (en) |
dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Math dbt:Mvar dbt:Nihongo dbt:R dbt:Reflist dbt:Short_description dbt:Self-published_inline dbt:Infobox_Algorithm dbt:Sorting |
dct:subject | dbc:Comparison_sorts dbc:Sorting_algorithms dbc:Heaps_(data_structures) dbc:Edsger_W._Dijkstra |
gold:hypernym | dbr:Algorithm |
rdf:type | dbo:Software yago:WikicatComparisonSorts yago:WikicatSortingAlgorithms yago:Ability105616246 yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Creativity105624700 yago:Event100029378 yago:Idea105833840 yago:Invention105633385 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 yago:WikicatDutchInventions |
rdfs:comment | Das Smoothsort-Sortierverfahren ist eine Variation von Heapsort, welche von Edsger W. Dijkstra 1981 entwickelt wurde. Der Vorteil liegt darin, dass es im Best-Case mit einem Aufwand von bei vorsortierten Folgen auskommt. Auf Grund der Kompliziertheit wird es aber selten benutzt. Dies liegt daran, dass es im Worst-Case und Average-Case mit einer Laufzeit von keine Verbesserung gegenüber dem Heapsort-Algorithmus mitbringt. (de) In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n), but it is not a stable sort. The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state. (en) In informatica lo Smoothsort (metodo) è un algoritmo di ordinamento particolarmente indicato per ordinare liste di dati già parzialmente ordinate. Lo Smoothsort è una variante dell'Heap sort sviluppata da Edsger Dijkstra nel 1981: come l'Heap sort anche lo Smoothsort presenta il limite computazionale massimo pari a O(n log n). Lo Smoothsort, però, si avvicina ad un tempo O(n) se i dati in ingresso sono già parzialmente ordinati, mentre l'Heap sort mediamente impiega O(n log n), indifferentemente dal livello di ordinamento iniziale. (it) Плавне сортування (англ. Smoothsort) — алгоритм сортування, різновид пірамідального сортування, розроблений Е. Дейкстрою 1981 року. Як і пірамідальне сортування, в найгіршому випадку має швидкодію О(n log n). Перевагою плавного сортування є те, що його швидкодія наближається до O(n), якщо вхідні дані частково відсортовано, в той час як швидкодія пірамідального сортування є незмінною та не залежить від стану вхідних даних. (uk) Algoritmo de ordenação relativamente simples. É um algoritmo de ordenação por comparação Smoothsort (método) é um algoritmo de ordenação de ordenação por comparação. É uma variação do heapsort e foi desenvolvido por Edsger Dijkstra em 1981. Como o heapsort, o limite superior do smoothsort é de O(n log n). A vantagem de smoothsort é que ele se aproxima de tempo O(n) se a entrada já tem algum grau de ordenação, enquanto a média do heapsort é de O(n log n), independentemente do estado inicial em termos de ordenação. (pt) Плавная сортировка (англ. Smoothsort) — алгоритм сортировки выбором, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную O(n log n). Преимущество плавной сортировки в том, что её сложность приближается к O(n), если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных. (ru) Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. C'est un tri de complexité en , tout comme le tri par tas dont il est inspiré, et le tri rapide dans la plupart des cas. Mais si les données sont déjà presque triées, il est de complexité en . Ce tri est alors plus rapide que le tri rapide. (fr) |
rdfs:label | Smoothsort (de) Smoothsort (fr) Smoothsort (it) Smoothsort (pt) Smoothsort (en) Плавная сортировка (ru) Плавне сортування (uk) |
owl:sameAs | freebase:Smoothsort yago-res:Smoothsort wikidata:Smoothsort dbpedia-de:Smoothsort dbpedia-fa:Smoothsort dbpedia-fr:Smoothsort dbpedia-it:Smoothsort dbpedia-pt:Smoothsort dbpedia-ru:Smoothsort dbpedia-sr:Smoothsort dbpedia-tr:Smoothsort dbpedia-uk:Smoothsort https://global.dbpedia.org/id/gZzp |
prov:wasDerivedFrom | wikipedia-en:Smoothsort?oldid=1098544685&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/Smoothsort.gif |
foaf:isPrimaryTopicOf | wikipedia-en:Smoothsort |
is dbo:wikiPageDisambiguates of | dbr:Smooth |
is dbo:wikiPageRedirects of | dbr:Poplar_sort dbr:Post-order_heap |
is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:List_of_data_structures dbr:List_of_Dutch_inventions_and_innovations dbr:Comparison_sort dbr:Leonardo_number dbr:Priority_queue dbr:Adaptive_sort dbr:Time_complexity dbr:Heapsort dbr:Sorting_algorithm dbr:Smooth dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Poplar_sort dbr:Post-order_heap |
is foaf:primaryTopic of | wikipedia-en:Smoothsort |