Selection sort (Ordenação por Seleção)

O algoritmo de ordenação por seleção é um dos métodos de ordenação mais intuitivos. Ele encontra repetidamente o elemento mínimo no array e traz esse elemento para a posição inicial. Em seguida, passa a procurar o elemento mínimo no subarray restante e repete esse processo até chegar ao fim do array.

a = [...]
for i in range(len(a)):                  # Devemos colocar o mínimo de a[i:] em a[i]
    min_idx = i                          # Índice do elemento mínimo
    for j in range(i + 1, len(a)):       # Encontrar o índice do elemento mínimo
        if a[j] < a[min_idx]:            # Se encontrarmos um elemento mais pequeno
            min_idx = j                  # Atualizar o índice do elemento mínimo
    a[i], a[min_idx] = a[min_idx], a[i]  # Trocar a[i] com a[min_idx]
print(a)

Em cada iteração, selecionamos o mínimo do subarray restante e trocamos o elemento atual com esse mínimo pelos respetivos índices. Caso o elemento atual já seja o mínimo, não haverá alteração, pois estaremos apenas a trocar o elemento consigo mesmo, o que não afeta o array.

O algoritmo de ordenação por seleção encontra o elemento mínimo do array e troca o índice atual por esse mínimo. Isso significa que a cada iteração percorremos todo o subarray restante para encontrar o mínimo (a função min analisa o array elemento a elemento para determinar o valor mínimo). Assim, o tempo total de execução do algoritmo consiste em n iterações que fazem cerca de n varreduras ⇒ operações no total.

Vamos simular o algoritmo em alguns arrays:

[4, 1, -1, 0, 2, 8]

i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]

i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]

i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]

i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]

i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]

i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]

[10, 5, 1, -1, -2, -7]

i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]

i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]

i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

[1, 2, 3, 4, 5]

i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]

Desafio

Dado n inteiros, ordena-os em ordem crescente usando selection sort.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 1000), que é o número de elementos no array.

A linha seguinte contém n inteiros separados por espaços ( ≤ ≤ ).

Saída

O programa deve imprimir o array de entrada ordenado em ordem crescente.

Exemplos

Entrada	Saída
5 5 5 3 2 3	2 3 3 5 5

Desafio

Entrada

Saída

Exemplos

Constraints

To check your solution you need to sign in

Sign in to continue