Ordenação por seleção

7.1 Definição da ordenação por seleção

Ordenação por seleção (Selection Sort) é um algoritmo de ordenação que encontra o menor elemento da parte não ordenada do array e troca ele com o primeiro elemento dessa parte. O processo se repete para os elementos restantes até que o array inteiro esteja ordenado.

Princípio de funcionamento:

1. Começamos com o primeiro elemento do array.
2. Encontramos o menor elemento na parte restante não ordenada do array.
3. Trocamos o menor elemento com o primeiro elemento da parte não ordenada.
4. Repetimos o processo para o próximo elemento até que todo o array esteja ordenado.

Processo passo a passo

1. Encontramos o menor elemento no array e trocamos com o primeiro elemento.
2. Repetimos o processo para o restante do array (começando do segundo elemento).
3. Continuamos o processo até que todo o array esteja ordenado.

Complexidade temporal e espacial da ordenação por seleção

Complexidade temporal:

• No pior caso: O(n^2) — acontece quando os elementos estão inicialmente ordenados em ordem inversa ou aleatória.
• No caso médio: O(n^2) — acontece para uma disposição aleatória dos elementos.
• No melhor caso: O(n^2) — mesmo se o array já estiver ordenado, o algoritmo ainda realiza as mesmas comparações.

Complexidade espacial:

O(1) — já que o algoritmo utiliza uma quantidade constante de memória adicional (apenas algumas variáveis para armazenar valores temporários).

7.2 Implementação do algoritmo de ordenação por seleção

A implementação do algoritmo é muito simples:

Passo 1: encontramos o menor elemento entre todos os elementos e trocamos com o primeiro.

Passo 2: encontramos o menor elemento entre todos os elementos, exceto o primeiro, e trocamos com o segundo.

Passo 3: encontramos o menor elemento entre todos os elementos, exceto o primeiro e o segundo, e trocamos com o terceiro.

Implementação em Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Encontramos o menor elemento na parte restante não ordenada do array
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Trocamos o menor elemento encontrado com o primeiro elemento da parte não ordenada
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Retornamos o array ordenado

# Exemplo de uso:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Array ordenado:", sorted_arr)
# Saída: Array ordenado: [11, 12, 22, 25, 64]

Exemplo de funcionamento do algoritmo:

1. Primeira passagem (i = 0):
   1. Encontramos o menor elemento (11) na parte não ordenada do array [64, 25, 12, 22, 11].
   2. Trocamos 11 com 64.
   3. Array: [11, 25, 12, 22, 64]
2. Segunda passagem (i = 1):
   1. Encontramos o menor elemento (12) na parte não ordenada do array [25, 12, 22, 64].
   2. Trocamos 12 com 25.
   3. Array: [11, 12, 25, 22, 64]
3. Terceira passagem (i = 2):
   1. Encontramos o menor elemento (22) na parte não ordenada do array [25, 22, 64].
   2. Trocamos 22 com 25.
   3. Array: [11, 12, 22, 25, 64]
4. Quarta passagem (i = 3):
   1. Encontramos o menor elemento (25) na parte não ordenada do array [25, 64].
   2. 25 já está no lugar certo, não é necessário trocar.
   3. Array: [11, 12, 22, 25, 64]

O algoritmo termina, pois todos os elementos estão ordenados.

2

Tarefa

Python SELF PT, nível 58, lição 2

Bloqueado

Ordenação por seleção

Ordenação por seleção

Abrir

2

Tarefa

Python SELF PT, nível 58, lição 2

Bloqueado

Ordenação de números

Ordenação de números

Abrir