A classificação é uma operação básica na qual os elementos de uma matriz são organizados em alguma ordem específica para aumentar sua capacidade de pesquisa. Em palavras simples, os dados são classificados para que possam ser facilmente pesquisados.
Gráfico de comparação
| Base para comparação | Tipo de Inserção | Seleção de seleção |
|---|---|---|
| Basic | Os dados são classificados inserindo os dados em um arquivo classificado existente. | Os dados são classificados selecionando e colocando os elementos consecutivos no local classificado. |
| Natureza | Estável | Instável |
| Processo a ser seguido | Os elementos são conhecidos de antemão, enquanto a localização para colocá-los é pesquisada. | O local é conhecido anteriormente enquanto os elementos são pesquisados. |
| Dados imediatos | A ordenação de inserção é uma técnica de ordenação ao vivo que pode lidar com dados imediatos. | Não pode lidar com dados imediatos, precisa estar presente no começo. |
| Melhor complexidade de casos | Em) | O (n 2 ) |
Definição de ordenação de inserção
A ordenação de inserção funciona inserindo o conjunto de valores no arquivo classificado existente. Ele constrói o array ordenado inserindo um único elemento por vez. Esse processo continua até que o array inteiro seja classificado em alguma ordem. O conceito primário por trás da inserção é inserir cada item em seu lugar apropriado na lista final. O método de classificação de inserção salva uma quantidade efetiva de memória.
Trabalho do tipo Inserção
- Ele usa dois conjuntos de matrizes em que um armazena os dados classificados e outros em dados não classificados.
- O algoritmo de classificação funciona até que haja elementos no conjunto não classificado.
- Vamos supor que existam 'n' elementos numéricos na matriz. Inicialmente, o elemento com índice 0 (LB = 0) existe no conjunto classificado. Os elementos restantes estão na partição não classificada da lista.
- O primeiro elemento da parte não classificada tem índice de matriz 1 (Se LB = 0).
- Após cada iteração, ele escolhe o primeiro elemento da partição não classificada e o insere no local apropriado no conjunto classificado.
Vantagens da classificação de inserção
- Facilmente implementado e muito eficiente quando usado com pequenos conjuntos de dados.
- O requisito de espaço de memória adicional de inserção de classificação é menor (ou seja, O (1)).
- É considerada uma técnica de ordenação ao vivo, pois a lista pode ser classificada conforme os novos elementos são recebidos.
- É mais rápido que outros algoritmos de classificação.
Exemplo:
Definição do tipo de seleção
A classificação de seleção executa a classificação pesquisando o número de valor mínimo e colocando-o na primeira ou na última posição de acordo com a ordem (crescente ou decrescente). O processo de procurar a chave mínima e colocá-la na posição correta é continuado até que todos os elementos sejam colocados na posição correta.
Trabalhando do Sort Selection
- Suponha uma matriz ARR com N elementos na memória.
- Na primeira passagem, a menor chave é pesquisada junto com sua posição e, em seguida, a ARR [POS] é trocada por ARR [0]. Portanto, ARR [0] é classificado.
- Na segunda passagem, novamente a posição do menor valor é determinada no subarray dos elementos N-1. Troque o ARR [POS] por ARR [1].
- No passe N-1, o mesmo processo é realizado para ordenar o número N de elementos.
Exemplo:
Principais diferenças entre ordenação de inserção e ordenação de seleção
- A classificação de inserção normalmente executa a operação de inserção. Pelo contrário, o tipo de seleção realiza a seleção e posicionamento dos elementos requeridos.
- Diz-se que a ordenação de inserção é estável enquanto a classificação de seleção não é um algoritmo estável.
- No algoritmo de classificação por inserção, os elementos são previamente conhecidos. Em contraste, a classificação de seleção contém a localização antecipadamente.
- A ordenação de inserção é uma técnica de classificação ativa em que os elementos que chegam são classificados imediatamente na lista, enquanto a classificação de seleção não pode funcionar bem com dados imediatos.
- A classificação por inserção tem o tempo de execução O (n) no melhor dos casos. Em contraste, a melhor complexidade de tempo de execução da classificação de seleção é O (n2).
Complexidade do tipo de inserção
A melhor complexidade de caso de inserção de inserção é O (n) vezes, ou seja, quando a matriz é classificada anteriormente. Da mesma forma, quando a matriz é classificada em ordem inversa, o primeiro elemento da matriz não classificada deve ser comparado com cada elemento no conjunto classificado. Portanto, no pior dos casos, o tempo de execução da ordenação Insertion é quadrático, ou seja, O (n2) . No caso médio também tem que fazer o mínimo (k-1) / 2 comparações. Portanto, o caso médio também possui tempo de execução quadrático O (n2).
Complexidade do tipo de seleção
Como o trabalho de seleção, o sort não depende da ordem original dos elementos no array, então não há muita diferença entre o melhor caso e a pior complexidade do tipo de seleção.
A classificação de seleção seleciona o elemento de valor mínimo, no processo de seleção todo o número 'n' de elementos é varrido; portanto, as comparações n-1 são feitas na primeira passagem. Então, os elementos são trocados. Da mesma forma na segunda passagem também para encontrar o segundo menor elemento que requer a varredura de elementos de resto n-1 e o processo é continuado até que toda a matriz seja ordenada.
Assim, a complexidade do tempo de execução da classificação da seleção é O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Conclusão
Entre os dois algoritmos de ordenação, a ordenação de inserção é rápida, eficiente, estável, enquanto a classificação de seleção só funciona eficientemente quando o pequeno conjunto de elementos está envolvido ou a lista é parcialmente classificada anteriormente. O número de comparações feitas por classificação de seleção é maior que os movimentos realizados, enquanto que na inserção classifica o número de vezes que um elemento é movido ou trocado é maior do que as comparações feitas.
