Classificar por inserções

Olá. Hoje continuamos a série de artigos que escrevi especificamente para o lançamento do curso "Algoritmos e estruturas de dados" da OTUS.

---

Introdução

A classificação de uma matriz é um dos primeiros problemas sérios estudados no curso clássico "Algoritmos e estruturas de dados" da disciplina de ciência da computação. Nesse sentido, as tarefas de escrever tipos e as perguntas correspondentes são frequentemente encontradas em entrevistas como estagiário ou desenvolvedor júnior.

Formulação do problema

Tradicionalmente, vale a pena iniciar a apresentação de soluções para o problema com sua declaração. Geralmente, a tarefa de classificação envolve a ordenação de uma matriz de números inteiros em ordem crescente. Mas, de fato, isso é um pouco simplista. Os algoritmos descritos nesta seção podem ser usados ​​para ordenar uma matriz de qualquer objeto entre os quais um relacionamento de ordenação seja estabelecido (ou seja, para quaisquer dois elementos que possamos dizer: o primeiro é maior que o segundo, o segundo é maior que o primeiro ou eles são iguais). Você pode classificar em ordem crescente e decrescente. Usaremos a simplificação padrão.

Classificar por inserções

A última vez que conversamos sobre um dos tipos mais simples - o tipo de seleção . Hoje vamos nos concentrar em um algoritmo um pouco mais complexo - tipo de inserção.

Descrição do algoritmo

A classificação de uma matriz por inserções é realizada da seguinte maneira: assim como no caso da classificação por seleção, a matriz é dividida em duas partes. Uma parte é chamada classificada e a outra não classificada. O algoritmo pressupõe percorrer toda a matriz, para que o comprimento da parte classificada se torne igual ao comprimento de toda a matriz. Em cada iteração, pegamos o primeiro elemento da parte não classificada da matriz e executamos a seguinte operação: enquanto nosso elemento é estritamente menor que o anterior, nós os trocamos. Em seguida, aumentamos o comprimento da parte classificada da matriz em um. Assim, movendo sucessivamente o elemento em estudo, conseguimos que ele se encaixe. Um exemplo de uma iteração é apresentado abaixo:

1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Implementação

Sugiro examinar a implementação desse algoritmo em C:

void insertionSortFunction(double array[], int size) {
    int i, j, temp;
    // i     ,   1,         
    for (i = 1; i < size; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < temp) {
                break;
            }
  
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}

Análise

Proponho analisar este algoritmo.



A maneira mais fácil de iniciar a análise é obter os assintóticos da memória. Independentemente do comprimento e da estrutura da matriz proposta para classificação, a memória é alocada apenas para dois contadores de loop e uma variável auxiliar usada para trocar dois valores de variável. Assim, é sempre verdade:

$$

$$M(n) = O(1)$$

...



Com o tempo, tudo é um pouco mais interessante. O corpo do loop interno recebe O (1), ou seja, não depende do tamanho da matriz que está sendo classificada. Isso significa que, para entender os assintóticos do algoritmo, é necessário contar quantas vezes esse corpo é executado. Mas o número de iterações do loop interno depende de quão bem ordenados (ou não ordenados) os elementos da matriz que estão sendo classificados. Vários casos precisam ser analisados ​​para análise.



O número mínimo de iterações é atingido se a matriz a ser classificada já estiver classificada. De fato, para cada iteração do loop for externo, ocorre exatamente uma iteração do loop interno. Este é o chamado melhor caso .

$$

$$T(n) = (n - 1) * O(1) = O(n)$$

Assim, a classificação é feita em tempo linear.



Na pior das hipóteses, presume-se que o número de iterações seja o maior, ou seja, a interrupção nunca é acionada. Na primeira iteração do loop externo, é executada uma iteração do loop interno. Na segunda iteração do loop externo, são realizadas 2 iterações do loop interno. Continuando o raciocínio, podemos concluir que, na última (n - 1) - ª) iteração do loop externo (n - 1), será executada a iteração do loop interno. Nós temos:

$$

$$T(n) = O(1) + 2 * O(1) + 3 * O(1) + ... + (n - 1) * O(1) = O(1 + 2 + 3 + ... + (n - 1)) = O(n * (n - 1) / 2) = O(n ^ 2)$$

Para realizar os cálculos, usamos as propriedades da notação O e a fórmula para a soma de uma progressão aritmética.



No caso médio, supõe-se que o número de iterações do loop interno para uma iteração específica do loop externo seja igual ao seu valor médio, ou seja, a expectativa matemática. Suponha que todos os números permitidos do disparo do loop interno sejam igualmente prováveis. Nesse caso, o número médio de iterações do loop interno é . Supõe-se que seja o número da iteração do loop externo. Agora, para calcular os assintóticos, você precisa calcular . Ou seja, contamos quantas vezes o corpo do loop interno é executado. Assim, chegamos .



Para resumir, os assintóticos de memória do algoritmo são

$$

$$O(1)$$

na melhor das hipóteses

$$

$$O(n)$$

e na média e nos piores casos

$$

$$O(n^2)$$

Portanto, essa classificação pertence à classe das classificações quadráticas .



Também é importante observar que a classificação por seleção é robusta nesta implementação . Deixe-me lembrá-lo de que a classificação é chamada de estável se a ordem dos elementos iguais não mudar durante sua execução. Essa propriedade não é muito importante para uma tarefa educacional como classificar uma matriz de números, mas se classificamos alguns objetos mais complexos com uma relação de ordenação estabelecida, pode ser importante. Podemos considerar um exemplo semelhante em algum momento da próxima vez que falarmos sobre classificação de base.

Resultado

Examinamos outro tipo quadrático: tipo de inserção e sua implementação robusta. A classificação é principalmente educacional, embora, na prática, possa ser aplicada devido a bons assintóticos: se você precisar adicionar novos dados a uma quantidade de dados grande o suficiente para que todos os dados sejam solicitados novamente, o loop for interno pode ser útil. Portanto, ele pode ser suportado por

$$

$$O(n)$$

ordem do volume de dados.

---

Saiba mais sobre o curso.

---