Revisão e teste de métodos de classificação. Parte I

Outro dia, nos comentários do VKontakte, briguei com um dos outros alunos do projeto. A essência da disputa era “quem vai ganhar” - um método sort()de uma classe java.util.Arraysou implementações auto-escritas de algoritmos simples: bolha , inserção , seleção , shell (algoritmo Shell). Para alguns, a resposta a esta questão pode ser óbvia, mas desde que surgiu a disputa, apesar de cada lado ter “fontes respeitadas” a favor do seu ponto de vista, decidiu-se realizar um estudo, esticando a massa cinzenta em o processo, implementando vários algoritmos. TL;DR: java.util.Arrays.sort() é incondicionalmente o líder em arrays de 100.000 elementos ou mais; com um tamanho menor, o método Shell às vezes pode competir com ele. O resto dos algoritmos considerados estão completamente vazios e só podem ser úteis sob algumas condições exóticas. Agora vamos ver como os arrays são classificados em nossos superdispositivos de silício.

Ordenação por seleção. Classificando por seleção

Vamos começar com o método mais simples e óbvio. A essência disso nos é perfeitamente demonstrada por Robert Sedgwick em sua vídeo-aula sobre o Coursera (vou citar a animação de lá que comprimi mal em um gif): View Percorrendo o array desde o primeiro elemento, em cada etapa nós procure o elemento mínimo do lado direito, com o qual trocamos o atual. Como resultado, reservamos a versão final do nosso array na forma ordenada. Aqui está o código que implementa este algoritmo em Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

A análise do algoritmo mostra que é necessário vasculhar o restante do array a cada passagem, ou seja, precisaremos exatamente de N + (N-1) + (N-2) + ... + 1 = N^ 2/2 comparações. Assim, a complexidade do algoritmo é O(N^2). O que isto significa? Isso significa que ao aumentar o número de elementos no array (N) em 2 vezes, aumentaremos o tempo de execução do algoritmo não em 2, mas em 2 ^ 2 = 4 vezes. Aumentando N em 10 vezes, aumentaremos o tempo de operação em 100 vezes e assim por diante. No meu laptop de 2012 com processador Core i3 rodando Ubuntu 14.4, obtive o seguinte tempo de atividade:

Classificação de inserção. Classificação de inserção

Aqui a ideia é um pouco diferente. Voltemos novamente à animação do Doutor Sedgwick: Ver O que está à frente ainda nem foi visto por nós, e tudo o que deixamos para trás permanece sempre em ordem. A questão é que “retornamos” cada novo elemento do array original ao início até que ele “repouse” em um elemento menor. Assim, novamente temos N passagens (para cada elemento do array original), mas em cada passagem, na maioria dos casos, não olhamos o resto inteiro, mas apenas uma parte. Ou seja, obteremos a opção 1 + (N-1) + (N-2) +… + N = N^2/2 somente se tivermos que retornar cada próximo elemento ao início, ou seja, no caso da matriz de entrada classificada “ao contrário” (azar, azar). No caso de um array já ordenado (aqui está a sorte) haverá um brinde completo - em cada passagem há apenas uma comparação e deixando o elemento no lugar, ou seja, o algoritmo funcionará em um tempo proporcional a N. A complexidade do algoritmo será determinado pelo pior caso teórico, ou seja, O(N^2). Em média, o tempo de operação será proporcional a N^2/4, ou seja, duas vezes mais rápido que o algoritmo anterior. Na minha implementação, devido ao uso não ideal da permutação, o tempo de execução foi maior que o da Seleção. Pretendo corrigir e atualizar a postagem em breve. Aqui está o código e o resultado de sua operação na mesma máquina:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Tipo de concha. Classificação de shell

Um cara esperto, Donald Schell, notou em 1959 que os casos mais caros no algoritmo de inserções são quando o elemento retorna muito longe do início do array: em alguma passagem retornamos o elemento ao início algumas posições , e em outra passagem quase por toda a matriz até o início é muito longo. É possível fazer isso de uma só vez, saltando por vários elementos? E ele encontrou esse caminho. Consiste na execução sequencial de classificações parciais especiais, geralmente chamadas de classificação d ou, de acordo com Sedgwick, classificação h (suspeito que h significa salto). A classificação 3, por exemplo, comparará o elemento em questão não com o anterior, mas pulará dois e comparará com aquele que está 3 posições atrás. Se alterado, ele irá compará-lo novamente com as posições do elemento 3 atrás e assim por diante. O resultado final é que o array resultante será “classificado em 3”, ou seja, a posição incorreta dos elementos será menor que 3 posições. Trabalhar com este algoritmo de inserção será fácil e agradável. A propósito, “1-sort” nada mais é do que apenas um algoritmo de inserção =) Ao aplicar h-sort sequencialmente ao array com valores h decrescentes, podemos classificar um array grande mais rapidamente. Esta é a aparência: Visualização O desafio aqui é como escolher a sequência correta de ordenações parciais. Em última análise, o desempenho do algoritmo depende disso. A mais comum é a sequência proposta por Donald Knuth: h = h*3 + 1, ou seja, 1, 4, 13, 40, ... e assim por diante até 1/3 do tamanho do array. Essa sequência oferece desempenho decente e também é fácil de implementar. A análise do algoritmo requer muita linguagem e está além da minha capacidade. A amplitude da análise também é determinada pelas muitas variantes das sequências h. Empiricamente, podemos dizer que a velocidade do algoritmo é muito boa – veja você mesmo: Um milhão de elementos em menos de um segundo! E aqui está o código Java com a sequência Knut.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Tipo de bolha. Método de bolha

Este é um clássico! Quase todo programador novato implementa esse algoritmo. É um clássico tão grande que o Dr. Sedgwick nem tinha animação para ele, então tive que fazer o trabalho sozinho. View Aqui, a cada passagem, percorremos o array do início ao fim, trocando os elementos vizinhos que estão fora de ordem. Como resultado, os elementos maiores “flutuam” (daí o nome) até o final do array. Iniciamos cada nova passagem com otimismo, esperando que o array já esteja classificado ( sorted = true). No final da passagem, se percebermos que cometemos um erro, iniciamos uma nova passagem. A dificuldade aqui é que, novamente, percorremos (quase) todo o array em cada passagem. A comparação ocorre em cada etapa, a troca ocorre em quase todas as etapas, o que torna esse algoritmo um dos mais lentos (se considerarmos os implementados racionalmente, e não o “shaking sort” e outros semelhantes). É interessante que formalmente a complexidade aqui também será igual a O(N^2), mas o coeficiente é muito maior que o de inserções e seleções. Código do algoritmo:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Tempo de operação: Sinta a diferença: mais de meia hora em um milhão de elementos! Conclusão: Nunca use este algoritmo!!!

Resumo da primeira parte

Como resultado, sugiro consultar a tabela geral desses algoritmos. Você também pode comparar com os resultados do método integrado java.util.Arrays.sort(). Parece algum tipo de mágica - o que poderia ser mais rápido que o Shell? Escreverei sobre isso na próxima parte. Lá veremos algoritmos de classificação rápida amplamente utilizados, bem como classificação por mesclagem, aprenderemos sobre a diferença nos métodos de classificação de arrays de primitivos e tipos de referência e também conheceremos uma interface muito importante neste assunto Comparable;) Abaixo você pode estudar um gráfico construído em escala logarítmica usando tabelas de dados. Quanto mais achatada a linha, melhor o algoritmo =) Para quem quiser baixar o projeto inteiro e fazer testes por conta própria, fique com o link: Java Até a próxima parte! =)