2 min read

Algoritmos de ordenação - O famoso Bubble Sort

Algoritmos de ordenação - O famoso Bubble Sort

O algoritmo

Uma implementação clássica, marcante e simples de ordenação de vetores, onde a cada iteração um elemento flutua para o topo. Humm! Dai vem o nome "Bolhas". Este é um assunto obrigatório em universidades ou cursos de programação.

Mesmo que grande parte dos nossos problemas sejam os frameworks e linguagens que escolhemos ter em nossas vidas, o estudo de algoritmo é essencial para desenvolvedores em geral, através desta dedicação, aprendemos técnicas que tornam nosso trabalho eficiente.

A implementação

Abaixo temos uma implementa√ß√£o do BubbleSort flex√≠vel que possibilita a ordena√ß√£o crescente ou decrescente atrav√©s do argumento (asc), a fun√ß√£o privada __should_swap__ foi definida para a classifica√ß√£o dos valores, decidindo a troca de posi√ß√Ķes no vetor.

O array.copy foi utilizado para evitar um efeito colateral (side-effect) no argumento vetor.
def bubble_sort(array, asc=True):
    output = array.copy()
    size = len(output)

    while size > 0:
        new_size = 0

        for current in range(1, size):
            prev = current - 1

            if __should_swap__(output, prev, current, asc):
                swap = output[prev]
                output[prev] = output[current]
                output[current] = swap

                new_size = current

        size = new_size

    return output


def __should_swap__(array, prev, current, asc):
    if asc:
        return array[current] < array[prev]
    else:
        return array[current] > array[prev]


def test_sort_asc():
    numbers = [5, 4, 2, 1, 3]
    result = bubble_sort(numbers, asc=True)

    assert numbers == [5, 4, 2, 1, 3]
    assert result == [1, 2, 3, 4, 5]


def test_bubble_sort_desc():
    numbers = [4, 5, 2, 1, 3]
    result = bubble_sort(numbers, asc=False)

    assert numbers == [4, 5, 2, 1, 3]
    assert result == [5, 4, 3, 2, 1]

Para validar o algoritmo use o pytest informando o nome do arquivo.

 pytest -rA bubble-sort.py

Teste de mesa

Os n√ļmeros da direita com menor valor s√£o movidos (ou flutuados) para esquerda, quando classificamos como ordem crescente.

Qual o problema do BubbleSort?

No melhor cen√°rio, o algoritmo retorna n de opera√ß√Ķes, onde n √© igual ao tamanho do vetor, por√©m no pior cen√°rio ele pode retornar n¬≤. O tamanho da lista ir√° determinar o tempo de processamento.

Para resolver estre problema existem diversos algoritmos para ordenação, com abordagens simples e sofisticadas:

Simples

Sofisticados

Finalizando

Este foi mais um exemplo de implementação de algoritmos, para relembrar ou adicionar ao seu kernel, até a próxima.