Bubble sort

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Algoritmos de ordenação

  • Estudado a fundo
  • Resolve como ordenar uma coleção desordenada em crescente/decrescente
  • Pode reduzir a complexidade de problemas
  • Alguns algoritmos de ordenação:
    • bubble sort
    • selection sort
    • insertion sort
    • merge sort
    • quicksort
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo.

  • Primeiro valor maior que o segundo
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. O primeiro e o segundo foram trocados.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o segundo elemento e outro para o terceiro.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o terceiro elemento e outro para o quarto.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o terceiro elemento e outro para o quarto. O terceiro e o quarto foram trocados.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o quarto elemento e outro para o quinto.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o quarto elemento e outro para o quinto. O quarto e o quinto foram trocados.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o quarto elemento e outro para o quinto. O quinto está em azul porque está ordenado.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. O último elemento está em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o segundo elemento e outro para o terceiro. O último elemento está em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o segundo elemento e outro para o terceiro. O segundo e o terceiro foram trocados. O último elemento está em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o terceiro elemento e outro para o quarto. O último elemento está em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o terceiro elemento e outro para o quarto. Os dois últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. Os dois últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. O primeiro e o segundo foram trocados. Os dois últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o segundo elemento e outro para o terceiro. Os dois últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o segundo elemento e outro para o terceiro. Os três últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. Os três últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. Os quatro últimos elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort

Um esquema de uma lista com números desordenados. Um ponteiro aponta para o primeiro elemento e outro para o segundo. Todos os elementos estão em azul.

  • Primeiro valor maior que o segundo
    • Troque
  • Segundo valor maior que o primeiro
    • Nada
Estruturas de Dados e Algoritmos em Python

Bubble sort - implementação

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Estruturas de Dados e Algoritmos em Python

Bubble sort - implementação

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Estruturas de Dados e Algoritmos em Python

Bubble sort - complexidade

  • Pior caso: $O(n^2)$
  • Melhor caso - versão não otimizada: $\Omega(n^2)$
  • Melhor caso - versão otimizada: $\Omega(n)$
  • Caso médio: $\Theta(n^2)$
  • Vai mal com listas grandes bem desordenadas
  • Vai bem:
    • listas grandes já ordenadas/quase ordenadas
    • listas pequenas
Estruturas de Dados e Algoritmos em Python

Vamos praticar!

Estruturas de Dados e Algoritmos em Python

Preparing Video For Download...