Python - Algoritmos de Classificação

A classificação refere-se a organizar os dados em um formato específico. O algoritmo de classificação especifica a maneira de organizar os dados em uma ordem específica. As ordens mais comuns são em ordem numérica ou lexicográfica.

A importância da classificação reside no fato de que a pesquisa de dados pode ser otimizada para um nível muito alto, se os dados forem armazenados de maneira classificada. A classificação também é usada para representar dados em formatos mais legíveis. Abaixo, vemos cinco dessas implementações de classificação em python.

Tipo de bolha
Mesclar Classificar
Ordem de inserção
Classificação Shell
Ordem de Seleção

Tipo de bolha

É um algoritmo baseado em comparação em que cada par de elementos adjacentes é comparado e os elementos são trocados se não estiverem em ordem.

def bubblesort(list):

# Swap the elements to arrange in order
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp


list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

Quando o código acima é executado, ele produz o seguinte resultado -

[2, 6, 11, 19, 27, 31, 45, 121]

Mesclar Classificar

A classificação por mesclagem primeiro divide a matriz em metades iguais e, a seguir, as combina de maneira classificada.

def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list
# Find the middle point and devide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half
    return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

Quando o código acima é executado, ele produz o seguinte resultado -

[11, 12, 22, 25, 34, 64, 90]

Ordem de inserção

A classificação por inserção envolve encontrar o lugar certo para um determinado elemento em uma lista classificada. Portanto, no início, comparamos os dois primeiros elementos e os classificamos comparando-os. Em seguida, escolhemos o terceiro elemento e encontramos sua posição adequada entre os dois elementos classificados anteriores. Dessa forma, vamos gradualmente adicionando mais elementos à lista já classificada, colocando-os em suas posições adequadas.

def insertion_sort(InputList):
    for i in range(1, len(InputList)):
        j = i-1
        nxt_element = InputList[i]
# Compare the current element with next one
		
        while (InputList[j] > nxt_element) and (j >= 0):
            InputList[j+1] = InputList[j]
            j=j-1
        InputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

Quando o código acima é executado, ele produz o seguinte resultado -

[2, 11, 19, 27, 30, 31, 45, 121]

Classificação Shell

O Shell Sort envolve a classificação de elementos que estão longe de ech other. Classificamos uma grande sublista de uma determinada lista e continuamos reduzindo o tamanho da lista até que todos os elementos sejam classificados. O programa abaixo encontra a lacuna igualando-a à metade do tamanho da lista e começa a classificar todos os elementos nela. Então, continuamos redefinindo a lacuna até que a lista inteira seja classificada.

def shellSort(input_list):
    
    gap = len(input_list) // 2
    while gap > 0:

        for i in range(gap, len(input_list)):
            temp = input_list[i]
            j = i
# Sort the sub list for this gap

            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j-gap
            input_list[j] = temp

# Reduce the gap for the next element

        gap = gap//2

list = [19,2,31,45,30,11,121,27]

shellSort(list)
print(list)

Quando o código acima é executado, ele produz o seguinte resultado -

[2, 11, 19, 27, 30, 31, 45, 121]

Ordem de Seleção

Na ordenação por seleção, começamos encontrando o valor mínimo em uma determinada lista e o movemos para uma lista ordenada. Em seguida, repetimos o processo para cada um dos elementos restantes na lista não classificada. O próximo elemento que entra na lista classificada é comparado com os elementos existentes e colocado em sua posição correta. Portanto, no final, todos os elementos da lista não classificada são classificados.

def selection_sort(input_list):

    for idx in range(len(input_list)):

        min_idx = idx
        for j in range( idx +1, len(input_list)):
            if input_list[min_idx] > input_list[j]:
                min_idx = j
# Swap the minimum value with the compared value

        input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]


l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

Quando o código acima é executado, ele produz o seguinte resultado -

[2, 11, 19, 27, 30, 31, 45, 121]

↰ Previous page Next page ↱