Ordenação por Seleção

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

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

Com as ideias acima 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 () 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: