Outra diferença considerável entre os dois é que o bubble sort é um algoritmo estável enquanto que o sort da seleção é um algoritmo instável. Um algoritmo é considerado fixo nos elementos com a mesma chave ocorrendo na mesma ordem em que estavam ocorrendo antes da classificação na lista ou matriz. Geralmente, algoritmos mais estáveis e rápidos usam memória adicional.
Gráfico de comparação
| Base para comparação | Tipo de bolha | Tipo de seleção |
|---|---|---|
| Basic | O elemento adjacente é comparado e trocado | O maior elemento é selecionado e trocado pelo último elemento (no caso de ordem crescente). |
| Melhor complexidade do tempo do caso | Em) | O (n 2 ) |
| Eficiência | Ineficiente | Maior eficiência em comparação com o tipo bolha |
| Estável | sim | Não |
| Método | Trocar | Seleção |
| Rapidez | Lento | Rápido em relação ao tipo de bolha |
Definição de Bubble Sort
A classificação de bolhas é o algoritmo iterativo mais simples que opera comparando cada item ou elemento com o item ao lado e trocando-os, se necessário. Em palavras simples, ele compara o primeiro e o segundo elemento da lista e troca-o, a menos que estejam fora da ordem específica. Da mesma forma, segundo e terceiro elemento são comparados e trocados, e essa comparação e troca vão para o final da lista. O número de comparações na primeira iteração é n-1, onde n é o número de elementos em uma matriz. O maior elemento estaria na enésima posição após a primeira iteração. E após cada iteração, o número de comparações diminui e, finalmente, a iteração ocorre apenas uma comparação.
Esse algoritmo é o algoritmo de classificação mais lento. A melhor complexidade de caso (quando a lista está em ordem) da classificação Bubble é de ordem n ( O (n) ), e a pior das hipóteses é O (n2) . No melhor dos casos, é da ordem n porque apenas compara os elementos e não os troca. Essa técnica também requer espaço adicional para armazenar a variável temporária.
Definição do tipo de seleção
A classificação de seleção alcançou um desempenho ligeiramente melhor e é eficiente do que o algoritmo de classificação de bolhas. Suponha que queremos organizar uma matriz em ordem crescente, então ela funciona encontrando o maior elemento e trocando-o com o último elemento, e repita o seguinte processo nos sub-arrays até que toda a lista seja ordenada.
Principais diferenças entre classificação de bolhas e ordenação de seleção
- Na classificação de bolhas, cada elemento e seu elemento adjacente são comparados e trocados, se necessário. Por outro lado, a classificação de seleção funciona selecionando o elemento e trocando esse elemento em particular com o último elemento. O elemento selecionado pode ser maior ou menor, dependendo da ordem, ou seja, crescente ou decrescente.
- A complexidade do pior caso é a mesma em ambos os algoritmos, ou seja, O (n2), mas a melhor complexidade é diferente. O tipo de bolha toma uma ordem de n tempo, enquanto a classificação de seleção consome uma ordem de n2 tempo.
- A classificação de bolhas é um algoritmo estável, em contraste, o tipo de seleção é instável.
- O algoritmo de classificação de seleção é rápido e eficiente em comparação com o bubble sort, que é muito lento e ineficiente.
Conclusão
O algoritmo de classificação de bolhas é considerado o algoritmo mais simples e ineficiente, mas o algoritmo de classificação de seleção é eficiente em comparação com a classificação de bolhas. A classificação de bolhas também consome espaço adicional para armazenar variáveis temporárias e precisa de mais trocas.
