| 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 17748 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:caption
|
- Smoothsort operating on an array which is mostly in order. The bars across the top show the tree structure. (en)
|
| dbp:class
| |
| dbp:data
| |
| dbp:optimal
|
- When the data is already sorted (en)
|
| dbp:space
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
