Algoritmos de Ordenação

Insertion Sort

Basicamente esse algoritmo ordena uma lista de valores por parte, comparando cada item com o resto e posicionando o elemento no lugar correto.

Obs.: Lembre de um conjunto de cartas na mão, onde você busca ordená-las em determinada ordem.

• Tempo de Execução: O(n²) - sendo "n" o tamanho da entrada; Pior e médio caso.

Funcionamento

Para entendermos o funcionamento, pensemos em uma lista de valores simples:

[5, 2]. Logicamente, para obtermos a ordenação ascendente dessa lista basta compararmos o último valor (2) com o primeiro valor (5), caso a comparação resulte em maior ou igual (> ou >=), indica que estamos com o valor na posição correta. No caso, temos como resultado da comparação: menor (<), o que implica na posição incorreta do item base de comparação (2).

Agora que sabemos a posição correta de cada um dos itens basta trocá-los de lugar.

 Exemplo mais complexo

Imaginemos uma lista contendo os seguintes valores: [5, 2, 3, 8, 9, 1].

Para que obtenhamos uma lista ordenada de forma ascendente, devemos seguir os seguintes passos.

 1. Olhamos para os dois primeiros elementos [5, 2], e aplicamos o que definimos acima, obtendo o seguinte resultado [2, 5], logo, a lista original passa a ser [2, 5, 3, 8, 9, 1];

  2. Nota-se que temos uma lista dividida em dois grupos de valores, um grupo que está ordenado e outro desordenado. Continuando a ordenação, pegaremos toda a nossa parte ordenada mais o item adjacente aos itens ordenados, porém do grupo dos desordenados. Ou seja, temos [2, 5, 3], a partir dessa sub lista, compararemos o último item com os primeiros, de modo a encontrarmos e posicionarmos o derradeiro item no seu lugar correspondente. Resultado: [2, 3, 5];

  3. Agora, facilmente entendemos o padrão a ser seguido para terminarmos a ordenação, e no final obtermos: [1, 2, 3, 5, 8, 9].

def insertionSort(arr): 
n = len(arr)

for i in range(1, n):
  for j in range(i, 0, -1):
    if arr[j] < arr[j-1] and j != 0:
      arr[j], arr[j-1] = arr[j-1], arr[j]
  
return arr


def insertionSort2(arr):
i = 1
while i < len(arr):
  temp = arr[i]
  troca = False
  j = i - 1
  while j >= 0 and arr[j] > temp:
    arr[j+1] = arr[j]
    troca = True
    j -= 1

  if troca:
    arr[j+1] = temp

  i += 1
return arr

Selection Sort

Basicamente esse algoritmo funciona usando a comparação entre os elementos de uma dada lista de valores. Primeiro procuramos pelo menor valor da lista, segundo um método de organização, e posicionamos esse elementos no início de nossa lista. Executamos essa instrução até obtermos a lista com os valores ordenados.

Obs.: Geralmente é o método que uma pessoa organiza valores visualmente, manualmente.

• Tempo de execução: O(n²) - sendo "n" o tamanho do dado de entrada. Pior e médio caso.

def selectionSort(*arrays):
array = []
for arr in arrays:
  for i in range(0, len(arr)):
    indMenor = i
    for j in range(i, len(arr)):
      if arr[j] < arr[indMenor]:
        indMenor = j
    
    aux = arr[i]
    arr[i] = arr[indMenor]
    arr[indMenor] = aux
  array.append(arr)
  
return array

Quick Sort

É um método de ordenação rápido e eficiente que adota a estratégia de divisão e conquista. A ideia é reordenar os valores de modo que os menores valores precedam os maiores.

• Complexidade: Pior Caso: ϴ(n²); Melhor Caso: O(n*log n)
• 
  

Funcionamento

 1. Escolha um elemento pivô;

 2. Particionamento (Operação de Partição): Reformulação da lista de modo que todos os elementos anteriores ao pivô sejam menores, e todos os posteriores sejam maiores que o pivô. No final restará duas sub listas não ordenadas como o pivô em sua posição correta

   3. Existem dois Métodos de Partição: Lomuto (fácil implementação / menos eficiente) e Hoare (difícil implementação / mais eficiente)

 4. Aplique o fenômeno da recursividade para ordenar as sub listas (sub lista dos elementos maiores que o pivô e sub lista dos elementos menores que o pivô)

Método de Lomuto: A ideia da partição usando o método de Lomuto é de colocar todos os elementos menores que o pivô imediatamente após o mesmo, e no final colocar o pivô depois de todos os menores. O pivô pode ser escolhido, como sendo o último ou primeiro elemento da lista.

Diversos métodos de melhorar a eficácia desse algoritmo foi testado, e entre eles, o uso de dois ou mais pivôs foi comprovado que a eficácia aumenta para grandes entradas de dados. (Yaroslavskiy - 2009) DualPivot QuickSort.

Nesse caso é utilizado dois pivôs, particionando um array de entrada em 3 partes.

Função Recursiva

def quickSort(arr, inicio=0, fim=None):
fim = fim if fim is not None else len(arr)

if inicio < fim:
  part = particao(arr, inicio, fim)
  quickSort(arr, inicio, part) # QuickSort na partição à esquerda do pivô
  quickSort(arr, part+1, fim) # QuickSort na partição à direita do pivô
return arr

Algoritmo de Partição

from random import randrange
def particao(arr, inicio, fim):
# Para uma partição aleatória descomente os seguintes códigos
#rand = randrange(inicio, fim)
#arr[rand], arr[fim - 1] = arr[fim - 1], arr[rand]

pivo = arr[fim - 1]
for i in range(inicio, fim):
  if arr[i] > pivo:
    fim += 1
  else:
    fim += 1
    inicio += 1
    arr[i], arr[inicio - 1] = arr[inicio - 1], arr[i]
return inicio - 1 # inicio - 1: É a posição final que o pivô ficou - 1, Temos o -1 para excluirmos o pivô na recursividade, pois ele já está ordenado

Trouxe apenas alguns dos principais algoritmos de ordenação. Esses textos são anotações antigas de estudos.

Links para o restante dos algoritmos de ordenação: https://colab.research.google.com/drive/1AzWjc2ri0r23gToy9luGe3KLzdvdMsh1?usp=sharing

Referências

Livro base (principalmente os capítulos 9 e 12): GOODRICH, M. T; TAMASSIA, R; GOLDWASSER, M, H. Data Structures & Algorithms in Python.

https://analyticsindiamag.com/how-evolutionary-algorithms-can-optimize-sorting/