| dbpedia-owl:abstract
|
- Combsort ist ein im April 1991 im BYTE magazine von S. Lacey und R. Box vorgestellter, vom Bubblesort abgeleiteter, nicht-stabiler In-place-Sortieralgorithmus, der eine Reihe von linear angeordneten Elementen (z. B. Zahlen) der Größe nach anordnet. Der Name leitet sich von engl. comb = Kamm ab, s. u.
- Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on bubble sort, and rivals algorithms like Quicksort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.). In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than one. (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort. ) The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3; see below), and the list is sorted with that value (rounded down to an integer if needed) for the gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.
- En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo publicado por la revista Byte en abril de 1991. El algoritmo comb sort mejora el algoritmo de ordenamiento de burbuja y rivaliza en velocidad con algoritmos más complejos como el Quicksort. La idea básica es eliminar tortugas, o pequeños valores cerca del final de la lista, ya que en el algoritmo de ordenamiento de burbuja esto reduce la velocidad de ordenamiento tremendamente. (Los conejos, grandes valores alrededor del inicio de la lista, no plantean un problema en el algoritmo de ordenamiento de burbuja. ) En el ordenamiento de burbuja, cuando dos elementos cualquiera se comparan, siempren tienen un espacio (distancia entre ellos) de 1. La idea básica del algoritmo comb sort es que el espacio pueda ser mucho mayor de uno. El ordenamiento Shell también se basa en esta idea, pero es una modificación del algoritmo de ordenamiento por inserción más que del algoritmo de ordenamiento de burbuja. El espacio se inicia como la longitud de la lista a ordenar dividida por el factor de encogimiento (generalmente 1,3; véase debajo), y la lista se ordena con este valor (redondeado a la baja a un entero si es necesario) para el espacio. Después el espacio se divide por el factor de encogimiento de nuevo, la lista se ordena con este nuevo espacio, y el proceso se repite hasta que el espacio es 1. En este momento, el algoritmo comb sort continua usando un espacio de 1 hasta que la lista está completamente ordenada. La etapa final del ordenamiento es así equivalente al algoritmo de ordenamiento de burbuja, pero en este momento la mayoría de las tortugas ya han sido tratadas, de manera que un algoritmo de ordenamiento de burbuja será eficiente.
- In Informatica il Comb sort è un algoritmo di ordinamento pubblicato per la prima volta da Stephen Lacey e Richard Box sul numero di aprile 1991 della rivista Byte. Il Comb sort rielabora le idee che Wlodzimierz Dobosiewicz applicò nel 1980 per rendere più efficiente lo shell sort utilizzando la funzione del bubble sort. Il Comb sort migliora l'algoritmo bubble sort e compete in velocità con algoritmi storicamente veloci come il Merge sort. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette "tartarughe", ovvero valori piccoli vicini alla fine della lista, essendo provato che in un bubble sort questi valori tendono spessissimo a scendere nella loro posizione in modo tremendamente lento. (i "conigli", ovvero grandi valori all'inizio della lista, non rappresentano un problema nel bubble sort perché generalmente vengono spostati molto velocemente). Nel bubble sort, quando vengono confrontati due elementi, essi hanno sempre un passo (distanza reciproca) pari ad 1. L'idea alla base del comb sort è che il possa possa essere anche maggiore (anche lo Shell sort è basato su questa idea, ma esso rappresenta una modifica dell'insertion sort piuttosto che del bubble sort). Il passo, o intervallo del confronto, è impostato inizialmente alla lunghezza dell'array da ordinare divisa per il fattore di riduzione (generalmente 1,3), e la lista viene ordinata con tale intervallo (arrotondato per difetto all'intero, se necessario). Terminato il primo passaggio il passo viene diviso nuovamente per il fattore di riduzione (arrotondato all'intero), e la lista viene ordinata con questo nuovo intervallo. Il processo si ripete finché il passo è pari a 1. A questo punto, il Comb sort continua ad usare un passo di 1 finché non si ha un ordinamento totale. Il passaggio finale dell'algoritmo è quindi equivalente ad un bubble sort, ma in questo modo molte "tartarughe" sono scomparse, ed in tal modo il bubble sort è molto più efficiente.
- コムソート（comb sort）は、Stephen LaceyとRichard Boxが1991年4月に開発したソートのアルゴリズムの一つ。コームソート、櫛（くし）ソートなどとも呼ばれる。 バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。
- Sortowanie grzebieniowe – wynaleziona w 1980 przez Włodzimierza DobosiewiczaSzablon:Fakt, odkryta ponownie i opisana w 1991 roku przez Stephena Lacey'a i Richarda Boxa metoda sortowania tablicowego. Jej główne cechy to: oparta na metodzie bubblesort prawdopodobnie złożoność wynosi O(n log n), statystycznie gorsza niż quicksort włączono empirię - współczynnik 1.3 wyznaczony doświadczalnie wariant podstawowy: za rozpiętość przyjmuje się długość tablicy, dzieli się rozpiętość przez 1.3, odrzuca część ułamkową bada się kolejno wszystkie pary obiektów odległych o rozpiętość (jeśli są ułożone niemonotonicznie - zamienia się je miejscami) wykonuje się powyższe w pętli dzieląc rozpiętość przez 1.3 do czasu, gdy rozpiętość osiągnie wartość 1. Gdy rozpiętość spadnie do 1 metoda zachowuje się tak jak sortowanie bąbelkowe. Tylko wtedy można określić, czy dane są już posortowane czy nie. W tym celu można użyć zmiennej typu bool, która jest ustawiana po zamianie elementów tablicy miejscami. Przerywane jest wykonywanie algorytmu, gdy podczas przejścia przez całą tablicę nie nastąpiła zamiana. Wariant Combsort 11: rozpiętość 9 i 10 zastępowane jest 11
- O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz. Mais tarde, foi redescoberto e popularizado por Stephen Lacey e Richard Box em um artigo publicado na revista Byte em Abril de 1991. O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort. A idéia básica é eliminar as tartarugas ou pequenos valores próximos do final da lista, já que em um bubble sort estes retardam a classificação tremendamente. (Coelhos, grandes valores em torno do início da lista, não representam um problema no bubble sort). O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente. Na Bubble sort, quando quaisquer dois elementos são comparados, eles sempre têm um gap (distância um do outro) de 1. A idéia básica do Comb sort é que a diferença pode ser muito mais do que um. (O Shell sort também é baseado nesta idéia, mas é uma modificação do insertion sort em vez do bubble sort). O gap (intervalo) começa como o comprimento da lista a ser ordenada dividida pelo fator de encolhimento (em geral 1,3; veja abaixo), e a lista é ordenada com este valor (arredondado para um inteiro se for necessário) para o gap. Então, a diferença é dividida pelo fator de encolhimento novamente, a lista é ordenada com este novo gap, e o processo se repete até que a diferença seja de 1. Neste ponto, o Comb sort continua usando um espaço de 1 até que a lista esteja totalmente ordenada. A fase final da classificação é, portanto, equivalente a um bubble sort, mas desta vez a maioria dos elementos "tartarugas" já foram tratados, assim o bubble sort será eficiente.
- 梳排序(Comb sort)是一種由Wlodzimierz Dobosiewicz於1980年所發明的不穩定排序算法，並由Stephen Lacey和Richard Box於1991年四月號的Byte雜誌中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在於消除烏龜，亦即在陣列尾部的小數值，這些數值是造成泡沫排序緩慢的主因。相對地，兔子，亦即在陣列前端的大數值，不影響泡沫排序的效能。 在泡沫排序中，只比較陣列中相鄰的二項，即比較的二項的間距(Gap)是1，梳排序提出此間距其實可大於1，改自插入排序的希爾排序同樣提出相同觀點。梳排序中，開始時的間距設定為陣列長度，並在迴圈中以固定比率遞減，通常遞減率設定為1.3。在一次迴圈中，梳排序如同泡沫排序一樣把陣列從首到尾掃描一次，比較及交換兩項，不同的是兩項的間距不固定於1。如果間距遞減至1，梳排序假定輸入陣列大致排序好，並以泡沫排序作最後檢查及修正。
- Сортировка расчёской — это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком). В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой идее, но она является модификацией сортировки вставками, а не сортировки пузырьком).
|
| rdfs:comment
|
- Combsort ist ein im April 1991 im BYTE magazine von S. Lacey und R. Box vorgestellter, vom Bubblesort abgeleiteter, nicht-stabiler In-place-Sortieralgorithmus, der eine Reihe von linear angeordneten Elementen (z. B. Zahlen) der Größe nach anordnet. Der Name leitet sich von engl. comb = Kamm ab, s. u.
- コムソート（comb sort）は、Stephen LaceyとRichard Boxが1991年4月に開発したソートのアルゴリズムの一つ。コームソート、櫛（くし）ソートなどとも呼ばれる。 バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。
- 梳排序(Comb sort)是一種由Wlodzimierz Dobosiewicz於1980年所發明的不穩定排序算法，並由Stephen Lacey和Richard Box於1991年四月號的Byte雜誌中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在於消除烏龜，亦即在陣列尾部的小數值，這些數值是造成泡沫排序緩慢的主因。相對地，兔子，亦即在陣列前端的大數值，不影響泡沫排序的效能。 在泡沫排序中，只比較陣列中相鄰的二項，即比較的二項的間距(Gap)是1，梳排序提出此間距其實可大於1，改自插入排序的希爾排序同樣提出相同觀點。梳排序中，開始時的間距設定為陣列長度，並在迴圈中以固定比率遞減，通常遞減率設定為1.3。在一次迴圈中，梳排序如同泡沫排序一樣把陣列從首到尾掃描一次，比較及交換兩項，不同的是兩項的間距不固定於1。如果間距遞減至1，梳排序假定輸入陣列大致排序好，並以泡沫排序作最後檢查及修正。
- Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on bubble sort, and rivals algorithms like Quicksort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously.
- En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo publicado por la revista Byte en abril de 1991. El algoritmo comb sort mejora el algoritmo de ordenamiento de burbuja y rivaliza en velocidad con algoritmos más complejos como el Quicksort.
- In Informatica il Comb sort è un algoritmo di ordinamento pubblicato per la prima volta da Stephen Lacey e Richard Box sul numero di aprile 1991 della rivista Byte. Il Comb sort rielabora le idee che Wlodzimierz Dobosiewicz applicò nel 1980 per rendere più efficiente lo shell sort utilizzando la funzione del bubble sort. Il Comb sort migliora l'algoritmo bubble sort e compete in velocità con algoritmi storicamente veloci come il Merge sort.
- Sortowanie grzebieniowe – wynaleziona w 1980 przez Włodzimierza DobosiewiczaSzablon:Fakt, odkryta ponownie i opisana w 1991 roku przez Stephena Lacey'a i Richarda Boxa metoda sortowania tablicowego.
- O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz. Mais tarde, foi redescoberto e popularizado por Stephen Lacey e Richard Box em um artigo publicado na revista Byte em Abril de 1991. O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort.
- Сортировка расчёской — это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке.
|
