Comb Sort

Comb Sort

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 ideia 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 ideia básica do Comb sort é que a diferença pode ser muito mais do que um. (O Shell sort também é baseado nesta ideia, 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.

Como tudo funciona

Mãos a obra:

    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;
    
    public class CombSort {
    
        public static void main(String[] args) {
            Scanner leia = new Scanner(System.in);
            ArrayList lista = new ArrayList<>();
            int cont = 1;
    
            for (int i = 0; i < 1000; i++) {
                Random rand = new Random();
                int n = rand.nextInt(1000);
                lista.add(n);
            }
    
            combSort(lista, lista.size());
    
            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }
    
        /* ---------------------- Algoritimo De Ordenação ---------------------- */
        public static void combSort(ArrayList lista, int size) {
            int gap = size;
            boolean swapped = true;
            while (gap != 1 || swapped == true) {
                gap = updateGap(gap);
                swapped = false;
                for (int i = 0; i < size - gap; i++) {
                    if (lista.get(i) > lista.get(i + gap)) {
                        int temp = lista.get(i);
                        lista.set(i, lista.get(i + gap));
                        lista.set(i + gap, temp);
                        swapped = true;
                    }
                }
            }
        }
    
        public static int updateGap(int gap) {
            gap = (gap * 10) / 13;
            if (gap < 1) {
                return 1;
            } else {
                return gap;
            }
        }
    }