Quick Sort

Quick Sort é um algoritmo eficiente de ordenação por divisão e conquista. Apesar de ser da mesma classe de complexidade do Merge Sort e do Heap Sort, o Quick Sort é na prática o mais veloz deles, pois suas constantes são menores. Contudo, é importante destacar de antemão que, em seu pior caso, o Quick Sort é O(n2), enquanto que o Merge Sort e o Heap Sort garantem n∗logn para todos os casos. A boa notícia é que há estratégias simples com as quais podemos minimizar as chances de ocorrência do pior caso.

O funcionamento do Quick Sort baseia-se em uma rotina fundamental cujo nome é particionamento. Particionar significa escolher um número qualquer presente no array, chamado de pivot, e colocá-lo em uma posição tal que todos os elementos à esquerda são menores ou iguais e todos os elementos à direita são maiores.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;
    
    public class QuickSort {
    
        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);
            }
    
            lista = quickSort(lista);
    
            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }
    
        /* ---------------------- Algoritimo De Ordenação ---------------------- */
    
        private static ArrayList quickSort(ArrayList lista) {
            int size = lista.size();
            if (lista.size() <= 1) {
                return lista;
            }
    
            int middle = (int) Math.ceil((double) size / 2);
            int pivot = lista.get(middle);
    
            ArrayList less = new ArrayList();
            ArrayList greater = new ArrayList();
    
            for (int i = 0; i < size; i++) {
                if (lista.get(i) <= pivot) {
                    if (i == middle) {
                        continue;
                    }
                    less.add(lista.get(i));
                } else {
                    greater.add(lista.get(i));
                }
            }
    
            return concatenate(quickSort(less), pivot, quickSort(greater));
        }
        
    
        private static ArrayList concatenate(ArrayList less, int pivot, ArrayList greater) {
    
            ArrayList aux = new ArrayList();
    
            for (int i = 0; i < less.size(); i++) {
                aux.add(less.get(i));
            }
    
            aux.add(pivot);
    
            for (int i = 0; i < greater.size(); i++) {
                aux.add(greater.get(i));
            }
    
            return aux;
        }
    }

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

Quick Sort	1.000	10.000	500.000	1.000.000
Bom	0.0104072	0.0069883	0.3392144	0.6794286
Médio	0.0019946	0.0112419	0.6202614	2.3110557
Ruim	0.0007434	0.005765	0.330906	0.6851811

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