Qual a principal característica básica (lógica/sistemática) de cada algoritmo a seguir: bubble sort, selection sort e insertion sort?
Passo 1
O enunciado pede para descrever a característica lógica ou sistemática de cada um dos três algoritmos de ordenação: bubble sort, selection sort e insertion sort. O conteúdo é algoritmos de ordenação elementares e precisaremos entender o fluxo de comparações e trocas que cada um realiza.
Passo 2
Bubble sort varre o vetor repetidamente, comparando pares de elementos vizinhos e trocando-os sempre que estiverem fora de ordem. A cada “passagem” pelo vetor, o maior (ou o menor, dependendo da ordem) elemento “borbulha” até uma das extremidades. Assim, após a primeira passagem, o maior elemento estará na última posição; após a segunda, o segundo maior estará na penúltima, e assim por diante.
Passo 3
Selection sort seleciona o menor (ou o maior) elemento do subvetor não ordenado e o coloca na posição correta por meio de uma única troca ao final de cada iteração. Em cada passo, ele varre o restante do vetor em busca do mínimo, marca sua posição e depois faz uma troca com o elemento que está no início do subvetor ainda não ordenado.
Passo 4
Insertion sort constrói um prefixo ordenado crescendo-o um elemento de cada vez. Para inserir o próximo elemento, ele “desce” dentro desse prefixo (movendo elementos maiores um lugar à direita) até encontrar a posição correta, onde então insere o elemento. Esse processo é parecido com o modo como alguém ordena cartas na mão.
Resposta
Bubble sort: borbulhamento de pares adjacentes por trocas sucessivas.
Selection sort: seleção do menor/maior em todo o subvetor e troca única para posicioná-lo.
Insertion sort: inserção de cada novo elemento no local certo deslocando o prefixo já ordenado.
Selection sort: seleção do menor/maior em todo o subvetor e troca única para posicioná-lo.
Insertion sort: inserção de cada novo elemento no local certo deslocando o prefixo já ordenado.