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

• Bubble sort
• Insertion sort
• Selection sort
• Comb sort

Sofisticados

• Merge sort
• Heapsort
• Shell sort
• Radix sort
• Gnome sort
• Counting sort
• Bucket sort
• Cocktail sort
• Timsort

Finalizando

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