Comb sort

Comb sort

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.

Contenido

Factor de encogimiento

El factor de encogimiento tiene un gran efecto en la eficiencia del algoritmo comb sort. En el artículo original, los autores sugierieron 1,3 después de probar algunas listas aleatorias y encontrarlo generalmente el más efectivo. Un valor muy pequeño reduce la velocidad del algoritmo porque se deben hacer más comparaciones, mientras que un valor demasiado grande puede que no elimine suficientes tortugas para que sea práctico.

El texto describe una mejora del algoritmo comb sort usando el valor base 1/(1-\frac{1}{e^\varphi}) \approx 1.247330950103979 como factor de encogimiento. También contiene una implementación en pseudocódigo con unas tablas de espacios predefinidos.

Combsort11

Con un factor de encogimiento alrededor de 1,3, sólo hay tres posibles maneras de que la lista de espacios acabe: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), o (11, 8, 6, 4, 3, 2, 1). Sólo el último de estos dos finales mata todas las tortugas antes de que el espacio se convierta en 1. Por lo tanto, se pueden hacer mejoras significativas en la velocidad si el espacio se establece en 11 siempre que sea 9 o 10. A esta variación se le llama Combsort11.

Si se usa cualquiera de la secuencias que comienza por 9 o 10, el paso final con un espacio de 1 es menos probable que haya ordenado los datos completamente, necesitando otro paso con un espacio de 1. Los datos están ordenados cuando no se hacen intercambios durante un paso con espacio = 1.

Ejemplo en pseudocódigo del algoritmo combsort11

function combsort11(array input)
    gap:= input.size //inicializar tamaño de espacio
    
    loop until gap = 1 and swaps = 0
        //actualizar el valor del espacio para el siguiente rastreo
        if gap > 1
            gap:= gap / 1.3
            if gap = 10 or gap = 9
                gap:= 11
            end if
        end if
        
i:= 0 swaps:= 0 //véase ordenamiento de burbuja para una explicación //un único "rastreo" sobre la lista de entrada loop until i + gap >= array.size if array[i] > array[i+gap] swap (array[i], array[i+gap]) swaps:= swaps + 1 end if i:= i + 1 end loop end loop end function

Véase también

  • Ordenamiento de burbuja, un algoritmo generalmente más lento, es la base del algoritmo comb sort.
  • Cocktail sort, un ordenamiento de burbuja bidireccional, es una variación del ordenamiento de burbuja que también trata el problema de las tortugas.

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • comb — [v1] arrange hair adjust, card, cleanse, curry, disentangle, dress, groom, hackle, hatchel, lay smooth, rasp, scrape, separate, smooth, sort, straighten, tease, untangle; concept 162 comb [v2] search by ransacking beat, beat the bushes*, examine …   New thesaurus

  • sort — [n] type, variety array, batch, battery, body, brand, breed, category, character, class, clutch, denomination, description, family, genus, group, ilk, kind, likes, likes of*, lot, make, nature, number, order, parcel, quality, race, set, species,… …   New thesaurus

  • comb — n 1. fine tooth comb, serration, serrated edge, toothed strip; hair comb, hairbrush, brush, currycomb; card; rake, harrow. 2. cock s comb, crest, tuft, Zool. caruncle, topknot; growth, Zool. beard, outgrowth, ridge, spine; feather, plume, panache …   A Note on the Style of the synonym finder

  • comb pottery — also called  combware        main pottery type of the Korean Neolithic Period (c. 3000–700 BC). Derived from a Siberian Neolithic prototype, the pottery is made of sandy clay, and its colour is predominantly brown. The vessel form found in early… …   Universalium

  • sort — Synonyms and related words: adjust, ailing, alphabetize, analyze, appraise, arrange, array, assess, assort, batch, battery, blood, body, body build, bolt, brand, break down, breed, bulk, cast, catalog, catalogue, categorize, category, character,… …   Moby Thesaurus

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Bubble sort — Infobox Algorithm class=Sorting algorithm data=Array time= О(n²) space= О(n) total, O(1) auxiliary optimal=NoBubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time… …   Wikipedia

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”