Ordenação por Bolha vs Ordenação por Seleção
Bubble sort é um algoritmo de ordenação que opera percorrendo a lista a ser ordenada repetidamente enquanto compara pares de elementos adjacentes. Se um par de elementos estiver na ordem errada, eles são trocados para colocá-los na ordem correta. Essa travessia é repetida até que não sejam necessárias mais trocas. A ordenação por seleção também é um algoritmo de ordenação, que começa encontrando o elemento mínimo na lista e trocando-o com o primeiro elemento. Este processo é repetido para o restante da lista, colocando os elementos trocados em ordem.
O que é Bubble Sort?
Bubble sort é um algoritmo de ordenação que opera percorrendo a lista a ser ordenada repetidamente enquanto compara pares de elementos adjacentes. Se um par de elementos estiver na ordem errada, eles são trocados para colocá-los na ordem correta. Essa travessia é repetida até que não sejam necessárias mais trocas (o que significa que a lista está classificada). Como os elementos menores da lista vêm para o topo quando uma bolha vem à superfície, ela recebe o nome de classificação de bolhas. Bubble sort é um algoritmo de ordenação muito simples, mas tem uma complexidade média de tempo de caso de O(n2) ao ordenar uma lista com n elementos. Devido a isso, o bubble sort não é adequado para ordenar listas com um grande número de elementos. Mas devido à sua simplicidade, a ordenação por bolhas é ensinada durante as introduções aos algoritmos.
O que é Seleção por Seleção?
Selection sort também é outro algoritmo de ordenação que começa encontrando o elemento mínimo na lista e trocando-o com o primeiro elemento. Em seguida, o elemento mínimo é encontrado a partir do restante da lista (do segundo elemento até o último elemento da lista) e trocado com o segundo elemento. Esse processo é repetido para o restante da lista, colocando os elementos trocados em ordem. Assim, na ordenação por seleção, em qualquer etapa do algoritmo, a lista é dividida em duas partes, onde uma parte contém elementos ordenados e a outra parte contém elementos não ordenados. À medida que o algoritmo avança, a lista ordenada cresce da esquerda para a direita. A ordenação por seleção também tem uma complexidade média de tempo de caso de O(n2). Portanto, também não é adequado para ordenar listas grandes.
Qual é a diferença entre Bubble Sort e Selection Sort?
Mesmo que os algoritmos de ordenação por bolhas e ordenação por seleção tenham complexidades de tempo médio de O(n2), a ordenação por bolhas é quase sempre superada pela ordenação por seleção. Isso se deve ao número de trocas necessárias pelos dois algoritmos (classificações de bolhas precisam de mais trocas). Mas devido à simplicidade do bubble sort, seu tamanho de código é muito pequeno. A estabilidade é outra diferença nesses dois algoritmos. Um algoritmo de classificação estável é um algoritmo de classificação que mantém a ordem dos registros se a lista contiver elementos com um valor igual. Nesse sentido, a ordenação por seleção não é um algoritmo estável, enquanto a ordenação por bolhas é um algoritmo estável.
