Selection Sort e Insertion Sort

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o primeiro elemento.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o primeiro elemento. O primeiro elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o segundo elemento. O primeiro elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o segundo elemento. O segundo elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o terceiro elemento. O segundo elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o quarto elemento. O segundo elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o quarto elemento. O quarto elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. Há um ponteiro apontando para o quinto elemento. O quarto elemento está em laranja.

Encontre o menor valor

Selection sort

Um esquema de uma lista com números fora de ordem. O quarto elemento está em laranja. Há duas setas indicando que o primeiro e o quarto elementos serão trocados.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em laranja. O primeiro e o quarto elementos foram trocados.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em azul e o segundo em laranja. Há um ponteiro apontando para o segundo elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em azul e o segundo em laranja. Há um ponteiro apontando para o terceiro elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em azul e o segundo em laranja. Há um ponteiro apontando para o quarto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em azul e o segundo em laranja. Há um ponteiro apontando para o quinto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul. Há um ponteiro apontando para o terceiro elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul e o terceiro está em laranja. Há um ponteiro apontando para o terceiro elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul e o terceiro está em laranja. Há um ponteiro apontando para o quarto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul e o quarto está em laranja. Há um ponteiro apontando para o quarto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul e o quarto está em laranja. Há um ponteiro apontando para o quinto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul e o quarto está em laranja. Há duas setas indicando que o terceiro e o quarto itens serão trocados.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul e o terceiro está em laranja. O terceiro e o quarto itens foram trocados.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul. Há um ponteiro apontando para o quarto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul, e o quarto está em laranja. Há um ponteiro apontando para o quarto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul, e o quarto está em laranja. Há um ponteiro apontando para o quinto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul, e o quinto está em laranja. Há um ponteiro apontando para o quinto elemento.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul, e o quinto está em laranja. Há duas setas indicando que o quarto e o quinto elementos serão trocados.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul, e o quarto está em laranja. O quarto e o quinto elementos foram trocados.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo, terceiro e quarto elementos estão em azul.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort

Um esquema de uma lista com números fora de ordem. Todos os elementos estão em azul.

Encontre o menor valor
Troque o menor valor com o primeiro elemento não ordenado

Selection sort - implementação

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

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

Selection sort - complexidade

Pior caso: $O(n^2)$
Caso médio: $\Theta(n^2)$
Melhor caso: $\Omega(n^2)$

Insertion sort

Um esquema de uma lista com números fora de ordem.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em azul e o segundo foi elevado acima dos outros.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro elemento está em azul e o segundo foi elevado acima dos outros. O primeiro elemento foi deslocado para a direita.

Insertion sort

Um esquema de uma lista com números fora de ordem. O segundo elemento está em azul. O elemento que foi elevado agora está na primeira posição.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro e o segundo elementos estão em azul. O terceiro elemento foi elevado acima dos outros.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul. O terceiro elemento foi elevado acima dos outros.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul. O terceiro elemento foi elevado acima dos outros. O terceiro elemento foi deslocado para a direita.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul. O terceiro elemento foi elevado acima dos outros. O terceiro e o segundo elementos foram deslocados para a direita.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo e terceiro elementos estão em azul. O terceiro elemento foi elevado acima dos outros. O terceiro, segundo e terceiro elementos foram deslocados para a direita.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo, terceiro e quarto elementos estão em azul.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo, terceiro e quarto elementos estão em azul. O quinto elemento foi elevado acima dos outros.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo, terceiro e quarto elementos estão em azul. O quinto elemento foi elevado acima dos outros. O quarto elemento foi deslocado para a direita.

Insertion sort

Um esquema de uma lista com números fora de ordem. O primeiro, segundo, terceiro e quarto elementos estão em azul. O quinto elemento foi elevado acima dos outros. O elemento que foi elevado agora está na quarta posição.

Insertion sort - implementação

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

Insertion sort - complexidade

Pior caso: $O(n^2)$
Caso médio: $\Theta(n^2)$
Melhor caso: $\Omega(n)$

Vamos praticar!

Estruturas de Dados e Algoritmos em Python