Working of the Bubble Sort
Lição 2 de 11 do curso Bubble Sort da Coddy.
Bubble sort (ordenação por flutuação) é um algoritmo de ordenação simples que itera pelos elementos de uma lista, compara elementos adjacentes e os troca se estiverem na ordem errada.
A passagem pela lista é repetida até que a lista esteja ordenada.
Um exemplo-
Temos que ordenar uma lista com 4 elementos: [3,4,2,1]
Primeira Passagem:
Compara os dois primeiros elementos
[3,4,2,1] -> [3,4,2,1] (Sem alteração, pois já estão ordenados)
Compara os próximos dois elementos
[3,4,2,1] -> [3,2,4,1] (Troca os elementos para deixá-los em ordem crescente)
Compara os próximos dois elementos
[3,2,4,1] -> [3,2,1,4] (Troca os elementos para deixá-los em ordem crescente)
Primeira Passagem concluída, o que você observou?
A lista está ordenada? -Não, certo?
Então, teremos que repetir o processo novamente.
Por favor, observe que com a primeira passagem, temos o elemento máximo ao final da lista. E é isso que tentaremos alcançar através das passagens subsequentes.
Segunda Passagem:
Compara os dois primeiros elementos
[3,2,1,4] -> [2,3,1,4] (Troca os elementos para deixá-los em ordem crescente)
Compara os próximos dois elementos
[2,3,1,4] -> [2,1,3,4] (Troca os elementos para deixá-los em ordem crescente)
Compara os próximos dois elementos
[2,1,3,4] -> [2,1,3,4] (Sem alteração, pois já estão ordenados)
Após a segunda passagem, note que os dois últimos elementos estão ordenados.
Terceira Passagem:
Compara os dois primeiros elementos
[2,1,3,4] -> [1,2,3,4] (Troca os elementos para deixá-los em ordem crescente)
Note que após esta passagem, obtivemos a lista desejada.
Então é assim que o BUBBLE SORT FUNCIONA!
Agora, vamos entender o algoritmo para o Bubble Sort na próxima lição.
Bons estudos!
Desafio
FácilCrie uma função chamada swap_list que recebe um array, o tamanho do array e dois índices. A função troca os elementos dos dois índices e retorna a nova lista.
Por exemplo:
list=[1,2,3,4] (baseado em 0)
n=4 (Número de elementos na lista)
i=1 j=3 (índices para trocar)
[1,2,3,4] -> [1,4,3,2]
Retorno: list= [1,4,3,2]
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
int* swap_list(int* arr, int arr_size, int n, int i, int j, int* returnSize) {
// Escreva o código aqui
*returnSize = n;
return arr;
}
Todas as lições de Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort AlgorithmPratique por conta própria: Compilador de C online