Diferença entre classificação de bolha e classificação de inserção

Classificação de bolhas vs Classificação de inserção

A classificação por bolha é um algoritmo de classificação que opera percorrendo a lista a ser classificada repetidamente enquanto compara pares de elementos adjacentes. Se um par de elementos estiver na ordem errada, eles serão trocados para colocá-los na ordem correta. Este percurso é repetido até que não sejam necessários mais swaps. 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. Esse processo é aplicado repetidamente até que a lista seja classificada.

O que é o Bubble Sort?

A classificação por bolha é um algoritmo de classificação que opera percorrendo a lista a ser classificada repetidamente enquanto compara pares de elementos adjacentes. Se um par de elementos estiver na ordem errada, eles serão trocados para colocá-los na ordem correta. Esse percurso é repetido até que não sejam necessários mais swaps (o que significa que a lista é classificada). Como os elementos menores da lista chegam ao topo quando uma bolha vem à superfície, ele recebe o nome de classificação da bolha. A classificação por bolha é um algoritmo de classificação muito simples, mas possui uma complexidade média de tempo de processamento de O (n2) ao classificar uma lista com n elementos. Por esse motivo, a classificação por bolhas não é adequada para classificar listas com um grande número de elementos. Porém, devido à sua simplicidade, o tipo de bolha é ensinado durante a introdução de algoritmos.

O que é classificação por inserção?

A classificação por inserção é outro 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é a lista ser classificada. Na classificação por inserção, a classificação é realizada no local. Portanto, após a i-ésima iteração do algoritmo, as primeiras entradas i + 1 da lista serão classificadas e o restante da lista não será classificado. 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 do caso de O (n2). Por esse motivo, a classificação por inserção também não é adequada para classificar listas grandes.

Qual é a diferença entre Classificação de bolhas e Classificação de inserção?

Mesmo que os algoritmos de classificação de bolhas e de inserção tenham complexidades médias em tempo de caso de O (n2), a classificação de bolhas quase sempre é superada pela classificação de inserção. Isso ocorre devido ao número de trocas necessárias pelos dois algoritmos (as classificações de bolhas precisam de mais trocas). Porém, devido à simplicidade da classificação por bolhas, seu tamanho de código é muito pequeno. Também existe uma variante de classificação de inserção chamada de classificação de shell, que possui uma complexidade de tempo de O (n3 / 2), o que permitiria que ele fosse utilizado praticamente. Além disso, a classificação por inserção é muito eficiente para classificar listas "quase classificadas", quando comparadas com a classificação por bolhas.