Ordenação por Bolha vs Ordenação por Inserçã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 classificação por inserção também é um algoritmo de classificação, que opera inserindo um elemento na lista de entrada na posição correta em uma lista que já está classificada. Este processo é aplicado repetidamente até que a lista seja ordenada.
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 é classificação por inserção?
Ordenação por inserção é outro algoritmo de ordenação, que opera inserindo um elemento na lista de entrada na posição correta em uma lista (que já está ordenada). Esse processo é aplicado repetidamente até que a lista seja classificada. Na ordenação por inserção, a ordenação é realizada no local. Portanto, após a iteração do algoritmo, as primeiras i+1 entradas da lista serão classificadas e o restante da lista será desclassificada. A cada iteração, o primeiro elemento na parte não classificada da lista será obtido e inserido no local correto na seção classificada da lista. A ordenação por inserção tem uma complexidade média de tempo de caso de O(n2). Devido a isso, a ordenação por inserção também não é adequada para ordenar listas grandes.
Qual é a diferença entre Bubble Sort e Insertion Sort?
Mesmo que os algoritmos de ordenação por bolhas e ordenação por inserção tenham complexidades de tempo médio de O(n2), a ordenação por bolhas é quase sempre superada pela ordenação por inserçã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. Também existe uma variante de ordenação por inserção chamada shell sort, que tem uma complexidade de tempo de O(n3/2), o que permitiria que ela fosse usada de forma prática. Além disso, a ordenação por inserção é muito eficiente para ordenar listas “quase ordenadas”, quando comparada com a ordenação por bolha.
