Coktail Sort

Cocktail shaker sort,também conhecido como bubble sort bidirecional,cocktail sort, shaker sort (o qual também pode se referir a uma variação do insertion sort), ripple sort, shuffle sort,ou shuttle sort, é uma variante do bubble sort, que é um algoritmo com não-estável e efetua Ordenação por comparação.

O algoritmo difere de um bubble sort no qual ordena em ambas as direções a cada iteração sobre a lista.

Esse algoritmo de ordenação é levemente mais difícil de implementar que o bubble sort, e e resolve o problema com os chamados coelhos e tartarugas no bubble sort. Ele possui performance levemente superior ao bubble sort, mas não melhora a performance assintótica; assim como o bubble sort, não é muito usado na prática (insertion sort é escolhido para ordenação simples), embora seja usado para fins didáticos.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;
    
    public class CoktailSort {
    
        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);
            }
    
            coktailSort(lista);
    
            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }
    
        /* ---------------------- Algoritimo De Ordenação ---------------------- */
        private static void coktailSort(ArrayList lista) {
            boolean swapped = true;
            int start = 0;
            int end = lista.size();
    
            while (swapped == true) {
                swapped = false;
    
                for (int i = start; i < end - 1; ++i) {
                    if (lista.get(i) > lista.get(i + 1)) {
                        int temp = lista.get(i);
                        lista.set(i, lista.get(i + 1));
                        lista.set(i + 1, temp);
                        swapped = true;
                    }
                }
    
                if (swapped == false) {
                    break;
                }
                swapped = false;
    
                end = end - 1;
    
                for (int i = end - 1; i >= start; i--) {
                    if (lista.get(i) > lista.get(i + 1)) {
                        int temp = lista.get(i);
                        lista.set(i, lista.get(i + 1));
                        lista.set(i + 1, temp);
                        swapped = true;
                    }
                }
                start = start + 1;
            }
        }
    }

Tempo de execução(em segundos) VS Qtd de nº no Array:

Coktail Sort	1.000	10.000	500.000	1.000.000
Bom	0.0003831	0.0029929	0.0572934	0.0548303
Médio	0.0848066	1.2535177	3326.2983418	22083.4725909
Ruim	0.0180384	1.1849084	3540.48832	13632.9493919

*A tabela representa a quantidade de numros utilizadas e o tempo de execução o processo de ordenação