Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodek Dobosiewicz in 1980. Later 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 complex 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.

PropertyValue
dbpprop:abstract
  • Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodek Dobosiewicz in 1980. Later 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 complex 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.
  • 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.
  • En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Stephen Lacey y Richard Box, que lo describieron en 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.
  • A fésűs rendezés (combsort) algoritmus egy tömb elemeinek sorba rendezésére. A buborékrendezés egy javított módszere. A buborékrendezés talán az összes rendezési algoritmus közül a legrosszabb, azonban egy egyszerű módosítással úgy felgyorsítható, hogy a gyorsrendezés sebességével vetekszik. Az eredeti fésűs rendezést Stephen Lacey és Richard Box fejlesztette, és a Byte Magazine publikálta 1991-ben.
  • In Informatica, comb sort è un algoritmo di ordinamento ideato da Stephen Lacey e Richard Box, nell' aprile 1991. Comb sort migliora l'algoritmo bubble sort e compete in velocità con algoritmi storicamente veloci come il Quicksort. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette tartarughe, ovvero valori piccoli vicino la 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 gap (distanza reciproca) pari ad 1. L'idea alla base del comb sort è che il gap può essere anche maggiore. (Anche lo Shell sort è basato su questa idea, ma esso rappresenta una modifica dell'insertion sort piuttosto che del bubble sort). L'intervallo di confronto comincia come la lunghezza dell'array da ordinare, divisa per il fattore shrink (generalmente 1,3), e la lista viene ordinata con tale intervallo (arrotondato per difetto all'intero, se necessario). Alchè esso viene diviso nuovamente per il fattore Shrink, e la lista viene ordinata con questo nuovo intervallo. Il processo si ripete finché il gap è 1. A questo punto, comb sort continua ad usare un gap di 1 finché non si ha 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 – wynaleziony w 1980 przez Włodzimierza Dobosiewicza, 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
  • Tarak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır. Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır. Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır. Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir. Kabarcık sıralaması algoritmasında iki öğe karşılaştırıldığında aralarındaki mesafe her zaman 1'dir. Başka bir deyişle, kabarcık sıralaması her zaman ardışık iki değeri karşılaştırır. Taraf sıralaması ise bunun aksine aralarındaki mesafe birden çok daha fazla olan öğeleri karşılaştırabilir. (Kabuk sıralaması da aynı düşünceyle tasarlanmıştır ancak kabuk sıralaması kabarcık sıralamasının değil seçmeli sıralamanın bir türevidir.)
  • Сортування гребінцем (lang-en|Comb sort) — спрощений алгоритм сортування, розроблений Влодеком Добошєвічем (Wlodek Dobosiewicz) у 1980 році, і пізніше заново слідженим та популяризованим Стефаном Лакеєм (Stephen Lacey) та Річардом Боксом (Richard Box), котрі написали про нього в журналі Byte Magazine у квітні 1991 р. Сортування гребінцем є поліпшенням алгоритму сортування бульбашкою, і конкурує у швидкодії з алгоритмом Швидке сортування. Основна його ідея полягає в тому, щоб усунути так званих "черепах", або малих значень ближче до кінця списку, оскільки у сортування бульбашкою вони сильно уповільнюють процес сортування. (Кролики та великі сортування на початку списку у сортуванні бульбашкою не являють собою проблеми). У сортуванні бульбашкою коли два елементи порівнюються, вони зажди мають розрив (відставнь один від одного) рівну 1. Основна ідея сортування гребінцем полягає у тому, що цей розрив може бути більший одиниці. (Алгоритм Сортування Шелла також базується на даній ідеї, однак, він є модифікацією алгоритму сортування вставками, а не сортування бульбашкою). Розрив починається зі значення, що рівне довжині списку, поділеного на фактор зменшення (за звичай, 1.3; див. нижче), і список сортується з урахуванням цього значення (при необхідності воно заокруглується до цілого). Потім розрив знову ділиться на фактор розриву, і список продовжує сортуватись з новим значенням, процес вродовжується до тих пір, доки розрив рівний 1. Далі список сортується з розривом рівним 1 до тих пір, доки не буде повністю відсортований. Таким чином, фінальний етап сортування аналогічний такому ж у сортуванні бульбашкою, однак, до цього "черепах" усувається.
dbpprop:class
dbpprop:data
dbpprop:hasPhotoCollection
dbpprop:optimal
  • ?
dbpprop:reference
dbpprop:space
  • O(1)
dbpprop:time
  • O(n \log n)
dbpprop:wikiPageUsesTemplate
dbpprop:wikibooksProperty
  • Algorithm implementation
  • Comb sort
  • Sorting/Comb sort
rdf:type
rdfs:comment
  • Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodek Dobosiewicz in 1980. Later 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 complex 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.
  • 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.
  • En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Stephen Lacey y Richard Box, que lo describieron en 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.
  • A fésűs rendezés (combsort) algoritmus egy tömb elemeinek sorba rendezésére. A buborékrendezés egy javított módszere. A buborékrendezés talán az összes rendezési algoritmus közül a legrosszabb, azonban egy egyszerű módosítással úgy felgyorsítható, hogy a gyorsrendezés sebességével vetekszik. Az eredeti fésűs rendezést Stephen Lacey és Richard Box fejlesztette, és a Byte Magazine publikálta 1991-ben.
  • In Informatica, comb sort è un algoritmo di ordinamento ideato da Stephen Lacey e Richard Box, nell' aprile 1991. Comb sort migliora l'algoritmo bubble sort e compete in velocità con algoritmi storicamente veloci come il Quicksort. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette tartarughe, ovvero valori piccoli vicino la fine della lista, essendo provato che in un bubble sort questi valori tendono spessissimo a scendere nella loro posizione in modo tremendamente lento.
  • コムソート（comb sort）は、Stephen LaceyとRichard Boxが1991年4月に開発したソートのアルゴリズムの一つ。コームソート、櫛（くし）ソートなどとも呼ばれる。 バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。
  • Sortowanie grzebieniowe – wynaleziony w 1980 przez Włodzimierza Dobosiewicza, odkryta ponownie i opisana w 1991 roku przez Stephena Lacey'a i Richarda Boxa metoda sortowania tablicowego.
  • Tarak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır. Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır. Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır.
rdfs:label
  • Comb sort
  • Combsort
  • Comb sort
  • Fésűs rendezés
  • Comb sort
  • コムソート
  • Sortowanie grzebieniowe
  • Tarak sıralaması
  • Сортування гребінцем
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of