Shellsort (original) (raw)
Shellsort ist ein von Donald L. Shell im Jahr 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert.
| Property | Value |
|---|---|
| dbo:abstract | Shellovo řazení, známé také pod anglickým jménem Shell sort nebo též řazení se snižujícím se přírůstkem, je řadicí algoritmus podobný algoritmu řazení vkládáním, který objevil a v roce 1959 publikoval . Shellovo řazení je nestabilní řadicí metoda (tj. nezachovává původní pořadí dvou prvků se stejným klíčem - mají-li prvky X a Y stejný klíč a v původním neseřazeném poli se prvek X vyskytuje před prvkem Y, ve výsledném seřazeném poli tomu tak po použití nestabilního řazení nemusí být). Asymptotická složitost je . Přesto je Shellovo řazení z kvadratických řadicích algoritmů nejvýkonnější. Časová složitost Shellova řazení je přibližně rovna . (cs) Shellsort ist ein von Donald L. Shell im Jahr 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert. (de) El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor . Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución. El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: 1. * El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". 2. * El ordenamiento por inserción es ineficiente, en general, porque mueve los valores solo una posición cada vez. El Algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados. (es) Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem. (en) Le tri de Shell ou Shell sort en anglais est un algorithme de tri. C'est une amélioration notable du tri par insertion au niveau de la vitesse d'exécution, mais ce tri n'est pas stable. Le principe de l'algorithme est simple mais l'étude du temps d'exécution est très complexe, et plusieurs problèmes sont toujours ouverts à ce sujet. Le nom vient de son inventeur (en) (1924-2015) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM. (fr) シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。 (ja) 셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다. 셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다. * 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다. * 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다. 셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다. 셸 정렬은 다음과 같은 과정으로 나눈다. 1. * 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다. 2. * 데이터를 다시 잘게 나누어서 삽입 정렬한다. 3. * 이렇게 계속 하여 마침내 정렬이 된다. 셸 정렬에서 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행한다. 그러나 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있다. 즉 N/2 보다는 N/3+1이 더 빠르다. (ko) Lo Shell sort (o Shellsort) è uno dei più vecchi algoritmi di ordinamento. È stato ideato nel 1959 da .L'algoritmo è veloce, facile da comprendere e da implementare, ma è difficile analizzarne il tempo di esecuzione. Lo Shell sort viene a volte chiamato "Shell-Metzner sort" in onore di Marlene Metzner che ne scrisse una primissima implementazione in FORTRAN. Venne per la prima volta chiamato Shell-Metzner in un articolo su Creative Computing nel 1976, ma Marlene Metzner disse di non volere che l'algoritmo portasse il suo nome. (it) Shellsort (of Shell sort) is een sorteeralgoritme dat in 1959 uitgevonden is door . Het is een snel algoritme dat ook makkelijk te implementeren is. (nl) Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo. Veja a versão em inglês desse mesmo link. (pt) Sortowanie Shella (ang. Shellsort) – jeden z algorytmów sortowania działających w miejscu i korzystających z porównań elementów. Można go traktować jako uogólnienie sortowania przez wstawianie lub sortowania bąbelkowego, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Na początku sortuje on elementy tablicy położone daleko od siebie, a następnie stopniowo zmniejsza odstępy między sortowanymi elementami. Dzięki temu może je przenieść w docelowe położenie szybciej niż zwykłe sortowanie przez wstawianie. Pierwszą wersję tego algorytmu, której zawdzięcza on swoją nazwę, opublikował w 1959 roku Donald Shell. Złożoność czasowa sortowania Shella w dużej mierze zależy od użytego w nim ciągu odstępów. Wyznaczenie jej dla wielu stosowanych w praktyce wariantów tego algorytmu pozostaje problemem otwartym. (pl) Shell Sort är en sorteringsalgoritm som uppfanns 1959 av . Algoritmen kan ses som en förbättring av andra enklare sorteringsalgoritmer, vanligtvis Insättningssortering. Det som gör att Shell Sort är effektivare än vanlig insättningssortering är att algoritmen tillåter jämförelse mellan två element som ligger långt ifrån varandra. (sv) Сортува́ння Ше́лла — це алгоритм сортування, що є узагальненням сортування включенням. Алгоритм базується на двох тезах: * Сортування включенням ефективне для майже впорядкованих масивів. * Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз. Тому сортування Шелла виконує декілька впорядкувань включенням, кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного. Сортування Шелла не є стабільним. (uk) Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской. (ru) 希爾排序（Shellsort），也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。 希爾排序是基於插入排序的以下兩點性質而提出改進方法的： * 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到的效率 * 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Sorting_shellsort_anim.gif?width=300 |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20150310043846/http:/www.sorting-algorithms.com/shell-sort https://www.youtube.com/watch%3Fv=CmPA7zE8mx0 http://www.cs.princeton.edu/~rs/shell/ |
| dbo:wikiPageID | 77355 (xsd:integer) |
| dbo:wikiPageLength | 31534 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122787988 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbr:Robert_Sedgewick_(computer_scientist) dbr:Bjorn_Poonen dbr:Paul_Vitányi dbr:Ricardo_Baeza-Yates dbr:Insertion_sort dbr:Introsort dbr:Comb_sort dbr:Gaston_Gonnet dbr:Greatest_common_divisor dbr:Thomas_N._Hibbard dbr:Andrew_Yao dbr:Linux_kernel dbr:Call_stack dbr:Comparison_sort dbr:Bubble_sort dbr:Bzip2 dbr:CPU_cache dbr:Adaptive_sort dbc:Comparison_sorts dbc:Sorting_algorithms dbr:Time_complexity dbr:UClibc dbr:Ming_Li dbr:Open_problem dbr:Kolmogorov_complexity dbr:Array_data_structure dbr:Bitonic_sorter dbr:Svante_Janson dbr:Coin_problem dbr:Donald_Knuth dbr:Donald_Shell dbr:C_standard_library dbr:Sorting_algorithm dbr:Sorting_network dbr:Coprime dbr:Embedded_systems dbr:In-place_algorithm dbr:Merge_sort dbr:OEIS dbr:Qsort dbr:Torsten_Suel dbr:Vaughan_Ronald_Pratt dbr:3-smooth dbr:File:Shell_sort_average_number_of_comparisons_(English).svg dbr:File:Shell_sorting_algorithm_color_bars.svg dbr:File:Sorting_shellsort_anim.gif |
| dbp:averageTime | depends on gap sequence (en) |
| dbp:bestTime | O (en) |
| dbp:caption | Shellsort with gaps 23, 10, 4, 1 in action (en) |
| dbp:class | dbr:Sorting_algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:date | 2015-03-10 (xsd:date) February 2021 (en) |
| dbp:optimal | No (en) |
| dbp:reason | There's a lot of discussion of divisibility, but I couldn't find this explicitly stated. E.g. p. 289 says "The increment sequences that we have discussed to this point are effective because successive elements are relatively prime. Another family of increment sequences is effective precisely because successive elements are not relatively prime." (en) |
| dbp:space | О total, O auxiliary (en) |
| dbp:time | O (en) |
| dbp:title | Animated Sorting Algorithms: Shell Sort (en) |
| dbp:url | https://web.archive.org/web/20150310043846/http:/www.sorting-algorithms.com/shell-sort |
| dbp:wikiPageUsesTemplate | dbt:OEIS_link dbt:Authority_control dbt:Cite_book dbt:Mvar dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Webarchive dbt:Wikibooks dbt:Unk dbt:Fv dbt:Infobox_Algorithm dbt:Sorting |
| dcterms:subject | dbc:Comparison_sorts dbc:Sorting_algorithms |
| gold:hypernym | dbr:Sort |
| rdf:type | owl:Thing yago:WikicatComparisonSorts yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:DataStructure105728493 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Food yago:Rule105846932 yago:SortingAlgorithm105847658 yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | Shellsort ist ein von Donald L. Shell im Jahr 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert. (de) Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem. (en) Le tri de Shell ou Shell sort en anglais est un algorithme de tri. C'est une amélioration notable du tri par insertion au niveau de la vitesse d'exécution, mais ce tri n'est pas stable. Le principe de l'algorithme est simple mais l'étude du temps d'exécution est très complexe, et plusieurs problèmes sont toujours ouverts à ce sujet. Le nom vient de son inventeur (en) (1924-2015) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM. (fr) シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。 (ja) Lo Shell sort (o Shellsort) è uno dei più vecchi algoritmi di ordinamento. È stato ideato nel 1959 da .L'algoritmo è veloce, facile da comprendere e da implementare, ma è difficile analizzarne il tempo di esecuzione. Lo Shell sort viene a volte chiamato "Shell-Metzner sort" in onore di Marlene Metzner che ne scrisse una primissima implementazione in FORTRAN. Venne per la prima volta chiamato Shell-Metzner in un articolo su Creative Computing nel 1976, ma Marlene Metzner disse di non volere che l'algoritmo portasse il suo nome. (it) Shellsort (of Shell sort) is een sorteeralgoritme dat in 1959 uitgevonden is door . Het is een snel algoritme dat ook makkelijk te implementeren is. (nl) Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo. Veja a versão em inglês desse mesmo link. (pt) Shell Sort är en sorteringsalgoritm som uppfanns 1959 av . Algoritmen kan ses som en förbättring av andra enklare sorteringsalgoritmer, vanligtvis Insättningssortering. Det som gör att Shell Sort är effektivare än vanlig insättningssortering är att algoritmen tillåter jämförelse mellan två element som ligger långt ifrån varandra. (sv) Сортува́ння Ше́лла — це алгоритм сортування, що є узагальненням сортування включенням. Алгоритм базується на двох тезах: * Сортування включенням ефективне для майже впорядкованих масивів. * Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз. Тому сортування Шелла виконує декілька впорядкувань включенням, кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного. Сортування Шелла не є стабільним. (uk) Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской. (ru) 希爾排序（Shellsort），也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。 希爾排序是基於插入排序的以下兩點性質而提出改進方法的： * 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到的效率 * 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位 (zh) Shellovo řazení, známé také pod anglickým jménem Shell sort nebo též řazení se snižujícím se přírůstkem, je řadicí algoritmus podobný algoritmu řazení vkládáním, který objevil a v roce 1959 publikoval . Shellovo řazení je nestabilní řadicí metoda (tj. nezachovává původní pořadí dvou prvků se stejným klíčem - mají-li prvky X a Y stejný klíč a v původním neseřazeném poli se prvek X vyskytuje před prvkem Y, ve výsledném seřazeném poli tomu tak po použití nestabilního řazení nemusí být). (cs) El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor . Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución. (es) 셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다. 셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다. * 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다. * 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다. 셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다. 셸 정렬은 다음과 같은 과정으로 나눈다. 1. * 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다. 2. * 데이터를 다시 잘게 나누어서 삽입 정렬한다. 3. * 이렇게 계속 하여 마침내 정렬이 된다. (ko) Sortowanie Shella (ang. Shellsort) – jeden z algorytmów sortowania działających w miejscu i korzystających z porównań elementów. Można go traktować jako uogólnienie sortowania przez wstawianie lub sortowania bąbelkowego, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Na początku sortuje on elementy tablicy położone daleko od siebie, a następnie stopniowo zmniejsza odstępy między sortowanymi elementami. Dzięki temu może je przenieść w docelowe położenie szybciej niż zwykłe sortowanie przez wstawianie. (pl) |
| rdfs:label | Shellovo řazení (cs) Shellsort (de) Ordenamiento Shell (es) Tri de Shell (fr) Shell sort (it) 셸 정렬 (ko) シェルソート (ja) Shellsort (nl) Shellsort (en) Sortowanie Shella (pl) Сортировка Шелла (ru) Shell sort (pt) Shell sort (sv) Сортування Шелла (uk) 希尔排序 (zh) |
| owl:sameAs | freebase:Shellsort yago-res:Shellsort wikidata:Shellsort dbpedia-az:Shellsort dbpedia-bg:Shellsort dbpedia-cs:Shellsort dbpedia-da:Shellsort dbpedia-de:Shellsort dbpedia-es:Shellsort dbpedia-et:Shellsort dbpedia-fa:Shellsort dbpedia-fr:Shellsort dbpedia-he:Shellsort http://hy.dbpedia.org/resource/Շելլի_տեսակավորում dbpedia-is:Shellsort dbpedia-it:Shellsort dbpedia-ja:Shellsort dbpedia-ko:Shellsort http://lt.dbpedia.org/resource/Šelo_rikiavimo_algoritmas http://ml.dbpedia.org/resource/ഷെൽ_സോർട്ട് dbpedia-nl:Shellsort dbpedia-no:Shellsort dbpedia-pl:Shellsort dbpedia-pt:Shellsort dbpedia-ru:Shellsort dbpedia-sk:Shellsort dbpedia-sl:Shellsort dbpedia-sr:Shellsort dbpedia-sv:Shellsort dbpedia-th:Shellsort dbpedia-tr:Shellsort dbpedia-uk:Shellsort http://uz.dbpedia.org/resource/Shell_sort dbpedia-zh:Shellsort https://global.dbpedia.org/id/518Pz |
| prov:wasDerivedFrom | wikipedia-en:Shellsort?oldid=1122787988&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Shell_sort_average_number_of_comparisons_(English).svg wiki-commons:Special:FilePath/Sorting_shellsort_anim.gif wiki-commons:Special:FilePath/Shell_sorting_algorithm_color_bars.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Shellsort |
| is dbo:wikiPageDisambiguates of | dbr:Shell |
| is dbo:wikiPageRedirects of | dbr:Shell_sort dbr:Gap_sort dbr:Shell's_method dbr:Shell's_sort dbr:Shell-Metzner_sort dbr:Shell_Sort |
| is dbo:wikiPageWikiLink of | dbr:Quicksort dbr:Robert_Sedgewick_(computer_scientist) dbr:List_of_algorithms dbr:Shell_sort dbr:Vaughan_Pratt dbr:Deaths_in_November_2015 dbr:Incompressibility_method dbr:Insertion_sort dbr:Introsort dbr:Comb_sort dbr:Thomas_N._Hibbard dbr:Comparison_sort dbr:Adaptive_sort dbr:Big_O_notation dbr:Coin_problem dbr:Donald_Shell dbr:Sorting_algorithm dbr:Shell dbr:List_of_unsolved_problems_in_computer_science dbr:Gap_sort dbr:Shell's_method dbr:Shell's_sort dbr:Shell-Metzner_sort dbr:Shell_Sort |
| is foaf:primaryTopic of | wikipedia-en:Shellsort |
