Clever Geek Handbook

Classificação da seleção

Olá. Escrevi este artigo 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.



Classificação da seleção



Um dos tipos mais simples é o tipo de seleção.



Descrição do algoritmo



A classificação de uma matriz por seleção é feita da seguinte maneira: 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. Dentro de cada iteração, encontramos o mínimo na parte não classificada da matriz e trocamos esse mínimo com o primeiro elemento da parte não classificada da matriz. Em seguida, aumentamos o comprimento da parte classificada da matriz em um. Um exemplo de uma iteração é apresentado abaixo:

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



Implementação



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



void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        // 
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}


Análise



Proponho analisar este algoritmo. 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. Na primeira iteração do loop externo, existem (n - 1) iterações do loop interno. Na segunda iteração do loop externo - (n - 2) iterações do loop interno. Continuando esse raciocínio, chegamos ao seguinte:

T(n)=(n−1)∗O(1)+(n−2)∗O(1)+...+O(1)=O((n−1)+(n−2)+...+1)=O((n−1)∗n/2)=O(n2)





No processo de cálculos, primeiro usamos as propriedades da notação O e, em seguida, a fórmula para calcular a soma de uma progressão aritmética.



Por ordem, também é necessário estimar a memória adicional necessária para executar o algoritmo. Tudo é muito mais simples aqui: alocamos memória apenas para os contadores de loop e uma variável - um buffer, que permite trocar 2 elementos do array. Portanto:

M(n)=O(1)





Como resultado da análise, chegamos à conclusão de que a complexidade de tempo do algoritmo depende do tamanho da matriz de entrada quadraticamente. Portanto, essa classificação pertence à classe das classificações quadráticas . O resultado da análise não depende do conteúdo da matriz: é correto na melhor das hipóteses, na pior e na média.



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 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 classificarmos 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.



Classificação de seleção frente e verso



A otimização do algoritmo implementado acima pode ser interessante: ao percorrer a parte não classificada da matriz, é possível procurar o máximo em paralelo com o elemento mínimo. Assim, após a iteração, você pode diminuir a parte não classificada da matriz não em um, mas em dois. O algoritmo não melhora assintoticamente, mas, no entanto, a velocidade de sua execução pode aumentar um pouco, o número de comparações também dobra.



Classificação de seleção recursiva



Como exercício, você pode tentar escrever um algoritmo não usando um loop, mas usando recursão. Em java, pode ser assim: 



public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}


Resultado



Analisamos um dos tipos quadráticos: tipo de seleção, uma implementação estável usando um loop, recursão, discutimos a otimização de algoritmos pela redução bidirecional da parte não classificada da matriz. A classificação é puramente educacional e não encontrou ampla aplicação na prática.





Se você quiser saber mais sobre o curso, convido todos a um seminário on-line gratuito, que será realizado em 10 de julho .





More articles:


All Articles