Ordenação por Seleção

A ideia por trás do algoritmo de ordenação por seleção é simples. Para um vetor $A$ de $n$ números, execute os seguintes passos:

  • A cada iteração do algoritmo, selecione o menor elemento do vetor $A$ e coloque-o em sua "posição correta".

  • Resolva o problema para os $n - 1$ elementos restantes.

A descrição acima nos dá uma ideia geral do funcionamento do algoritmo, mas ela é um pouco vaga (tão vaga que ela sequer contém uma descrição precisa do que seria a posição correta de um elemento qualquer). Vejamos uma descrição um pouco mais precisa (mas ainda não ideal):

  • Faça i = 0

  • Repita n vezes: + Selecione o menor elemento do vetor V, a partir da posição i + Coloque esse elemento em V[i] + Incremente i

Seguindo as regras acima, a cada iteração $i$ do algoritmo, todos os elementos à esquerda do índice $i$ estarão ordenados, e nenhum elemento à direita do elemento no índice $i$ é menor que os elementos à esquerda de $i$.

A partir dessa descrição fica mais fácil entender qual é a "posição correta" de um dado elemento. Com essas ideias em mente, podemos implementar o algoritmo de ordenação por seleção da seguinte forma:

import random

def ordenacao_selecao(A):
    n = len(A)
    # Percorre o arranjo A.
    for i in range(n):
        # Encontra o elemento mínimo em A.
        minimo = i
        for j in range(i + 1, n):
            if A[minimo] > A[j]:
                minimo = j
        # Coloca o elemento mínimo na posição correta.
        A[i], A[minimo] = A[minimo], A[i]

A = random.sample(range(-10, 10), 10)
print("Arranjo não ordenado: ", A)

ordenacao_selecao(A)

print("Arranjo ordenado:", A)
Arranjo não ordenado:  [9, 7, 3, -7, -9, -4, 0, 5, -10, -8]
Arranjo ordenado: [-10, -9, -8, -7, -4, 0, 3, 5, 7, 9]

O algoritmo de ordenação por seleção possui complexidade quadrática ($O(n^2)$) no número de elementos do vetor de entrada, é um algoritmo in-place, mas não é estável.

Se você quiser acompanhar visualmente a execução do algoritmo de ordenação por seleção, veja o excelente vídeo abaixo, feito pelo pessoal do site Algo-Rythmics:

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo