O que é classificação?

Classificação refere-se ao processo de organização de dados em uma ordem específica, normalmente em ordem crescente ou decrescente, com base em um relacionamento linear entre os itens de dados.

Por que precisamos de classificação?

A classificação é crucial ao trabalhar com dados estruturados porque permite a recuperação eficiente de dados, simplifica a análise de dados e aprimora o gerenciamento geral de dados.

Algoritmos de classificação

Esta postagem cobre os seguintes algoritmos de classificação: classificação por bolha, classificação por seleção, classificação por inserção, classificação por mesclagem e classificação rápida.

Classificação por bolha

Bubble Sort percorre repetidamente o array, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. Este processo continua até que o array seja classificado, com elementos maiores "borbulhando" até o final.

Algoritmo

Etapa 1: começar
Etapa 2: i = 0
Etapa 3: se i Etapa 4: j = 0
Etapa 5: se j Passo 6: se array[j] > array[j 1], vá para o Passo 7; senão vá para a Etapa 8
Etapa 7: trocar array[j] e array[j 1]
Passo 8: incremento j; vá para a etapa 5
Passo 9: incremento i; vá para a Etapa 3
Etapa 10: Fim

Código

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Complexidade de tempo

Melhor caso: O(n)
Caso médio: O (n ^ 2)
Pior caso: O (n ^ 2)

Ordenação por seleção

Selection Sort encontra o menor valor na parte não classificada da matriz e o coloca no início dessa parte.

Algoritmo

Etapa 1: começar
Etapa 2: i = 0
Etapa 3: se i Etapa 4: valor_mínimo = i; j = eu 1
Etapa 5: se j Etapa 6: se array[valor_mínimo] > array[j], vá para a Etapa 7; senão vá para a Etapa 8
Etapa 7: valor_mínimo = j
Passo 8: incremento j; vá para a etapa 5
Etapa 9: trocar array[valor_mínimo] e array[i]
Passo 10: incremento i; vá para a Etapa 3
Etapa 11: Fim

Código

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  Complexidade de tempo


Melhor caso: O(n^2)

Caso médio: O (n ^ 2) 

Pior caso: O (n ^ 2) 


  
  
  Classificação de inserção


Insertion Sort constrói a matriz classificada, um elemento por vez, pegando cada elemento da parte não classificada e inserindo-o na posição correta na parte classificada.


  
  
  Algoritmo


Etapa 1: começar

Etapa 2: eu = 1

Etapa 3: se i 
Etapa 4: chave = arr[i]

Etapa 5: j = i - 1

Passo 6: se j >= 0 e arr[j] > key, vá para o Passo 7; senão vá para a Etapa 10

Etapa 7: arr[j 1] = arr[j]

Etapa 8: diminuir j em 1

Etapa 9: vá para a Etapa 6

Etapa 10: arr[j 1] = chave

Passo 11: incrementar i em 1; vá para a Etapa 3

Etapa 12: Fim


  
  
  Código




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  Complexidade de tempo


Melhor caso: O(n)

Caso médio: O (n ^ 2) 

Pior caso: O (n ^ 2) 


  
  
  Mesclar classificação


Merge Sort é um algoritmo de divisão e conquista que divide recursivamente a matriz em submatrizes menores, classifica-as e depois as mescla novamente.


  
  
  Algoritmo


Algoritmo de classificação de mesclagem


Etapa 1: começar

Etapa 2: se comprimento (array) 
Etapa 3: ponto_médio = comprimento(array) // 2

Etapa 4: left_half = array[:mid_point]

Etapa 5: right_half = array[mid_point:]

Etapa 6: sorted_left = merge_sort(left_half)

Etapa 7: sorted_right = merge_sort(right_half)

Etapa 8: retornar mesclagem(sorted_left, sorted_right)

Etapa 9: Fim

Função de mesclagem


Etapa 1: começar

Etapa 2: sorted_merge = []

Etapa 3: l = 0, r = 0

Passo 4: se l 
Passo 5: se esquerda[l] 
Etapa 6: adicione left[l] a sorted_merge; incrementar l em 1

Etapa 7: adicione right[r] a sorted_merge; incrementar r em 1

Etapa 8: vá para a Etapa 4

Passo 9: se l 
Etapa 10: adicione left[l] a sorted_merge; incrementar l em 1 

Etapa 11: vá para a Etapa 9

Passo 12: se r 
Etapa 13: adicione right[r] a sorted_merge; incrementar r em 1

Etapa 14: vá para a Etapa 12

Etapa 15: Retornar sorted_merge

Etapa 16: Fim


  
  
  Código




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  Complexidade de tempo


Melhor caso: O(n log n)

Caso médio: O (n log n) 

Pior caso: O (n log n) 


  
  
  Classificação rápida


Quick Sort é um algoritmo de classificação eficiente e local que usa uma abordagem de dividir e conquistar. Ele seleciona um elemento pivô e particiona a matriz em torno do pivô de modo que os elementos menores que o pivô fiquem à sua esquerda e os elementos maiores que o pivô fiquem à sua direita. Este processo é então aplicado recursivamente às submatrizes.


  
  
  Algoritmo


Classificação rápida


Etapa 1: começar

Passo 2: Se baixo 
Etapa 3: pivot_index = partição(arr, baixo, alto)

Etapa 4: quicksort(arr, low, pivot_index - 1)

Etapa 5: quicksort(arr, pivot_index 1, high)

Etapa 6: Fim 

Função de partição


Etapa 1: começar

Etapa 2: pivô = arr[high]

Etapa 3: esquerda = baixa, direita = alta - 1

Etapa 4: se esquerda 
Etapa 5: se arr[esquerda] > pivô e arr[direita] 
Etapa 6: se arr[esquerda] 
Etapa 7: se arr[right] >= pivô, diminua à direita

Etapa 8: vá para a Etapa 4

Etapa 9: troque arr[esquerda] e arr[alto]

Etapa 10: retornar à esquerda

Etapa 11: Fim 


  
  
  Código




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  Complexidade de tempo


Melhor caso: O(n log n)

Caso médio: O (n log n) 

Pior caso: O (n ^ 2)