Algoritmos de ordenação - O famoso Bubble Sort

Algoritmos de ordenação - O famoso Bubble Sort

William Sena

Publicado por William Sena

22 Setembro, 2017Leia em 3 minutos

Introdução

Você que já cursou ou está em algum curso que envolve lógica de programação, provavelmente já passou por esta implementação.

Dependendo do momento em que esta aula foi cursada, você provavelmente se questionou a necessidade de aprender isso, se a maioria das linguagens possui um método sort pronto para atender esta demanda.

Vamos pensar um pouco - Telecurso 2000

Primeiramente algoritmos são ótimos para treinar o raciocínio lógico e existem alguns cenários que você provavelmente precisaria de uma implementação de ordenação, por exemplo:

  • Desenvolvimento de jogos - Jogos precisam de alta performance e em alguns cenários de baixo nível, simplesmente o método sort do array pode não existir ou não ser performático. Neste caso é importante que você conheça algoritmos de ordenação;

  • Banco de dados - Imagine que você subiu de nível e está criando um banco de dados, o JoãoDB, com grandes poderes grandes responsabilidades, a ordenação é sua responsabilidade.

  • Machine learning - Um assunto que está no hype, não precisamos comentar que é imprescindível dominar algoritmos.

via GIPHY

Algoritmos de Ordenação

Existem diversos algoritmos de ordenação desde os mais simples como:

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

Até os algoritmos mais sofisticados:

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

O Bubble Sort

É um dos mais simples e fáceis de ser explicado, por este motivo é um dos algoritmos com menor performance. A lógica do algoritmo é simples, a cada passagem do vetor o elemento com menor valor de acordo do tipo ordenação, deve ser flutuado para o topo, este processo originou o nome Bubble Sort.

Exemplo de ordenação Bubble Sort

(***) Veja que os números da direita com menor valor são flutuados para esquerda

Implementação

Segue uma implementação em Python de uma classe de vetor ordenável ArraySortable

class ArraySortable(object):
        
    def __init__(self, array):
        self.array = array
        self.length = len(self.array)

    def bubble_sort(self, asc=True):
        n = self.length
        
        while n > 0:            
            newn = 0
            
            # Loop do primeiro registro até N, N é o tamanho do vetor, alterado por newn a cada troca.
            for i in range(1, n):
                # Caso True executa a troca e altera o valor de N
                if self.__swap(i-1, i, asc):
                    newn = i
                    
            n = newn
               

    def __swap(self, left, right, asc):
        swap = None
        ascending = asc and self.array[right] < self.array[left]
        descending = not asc and self.array[right] > self.array[left]
                
        if ascending or descending:
            # O elemento é flutuado para o topo            
            swap = self.array[left]
            self.array[left] = self.array[right]
            self.array[right] = swap
        
        return swap != None
    

    def to_output(self):
        return [self.array[i] for i in range(foo.length)]
    
foo = ArraySortable([5, 4, 2, 1, 3])
print('Input: ', foo.to_output())

foo.bubble_sort()
print('Sort asc: ', foo.to_output())

foo.bubble_sort(False)
print('Sort desc: ', foo.to_output())

O método bubble_sort executa dois loop, um atende a condição n>0, n é a igual última posição do vetor trocada newn, caso não ocorra a troca de elementos n será zero e o vetor já está ordenado, fim da ordenação.

Caso contrário ordena da posição inicial até a última troca n, o parâmetro asc define se a ordenação será crescente ou decrescente, caso asc=True e o elemento da esquerda é maior que o elemento da direta, o elemento da direita é flutuado para esquerda através do método __swap, caso asc=False os elementos com maior valor são flutuados.

Desta forma a cada iteração, ocorre a comparação da posição inicial é até a última troca encontrada.

Qual o problema do BubbleSort?

No melhor cenário, o algoritmo retorna n de operações, n é igual ao tamanho do vetor, porém no pior cenário ele pode retornar , ou seja, para uma lista pequena não seria um problema para o processamento, mas vamos imaginar uma lista com mil, dez mil, milhões, realmente o tempo de processamento seria absurdo.

Por este motivo existem diversos algoritmos para ordenação complexos porém performáticos.

Finalizando

Este foi um exemplo prático de implementação do algoritmo Bubble Sort, até a próxima.

via GIPHY

Inscreva-se em nossa lista

E receba por email novos conteúdos.