Algoritmos de Ordenação: Insertion Sort, Selection Sort e Mais

Algoritmos de Ordenação em Python

1. Insertion Sort

Pseudocódigo:

Procedimento InsertionSort(v: vetor, n: inteiro):
  Para j = 1 até n faça:
    X = v[j]
    I = j-1
    Enquanto i >= 0 e V[i] > x faça:
      V[i+1] = v[i]
      I = i-1
    Fim-enquanto
    V[i+1] = x
  Fim-para
Fim-procedimento

Implementação em Python:

def insertion_sort(V):
  for j in range(1, len(V)):
    X = V[j]
    I = j-1
    while i >= 0 and V[i] > X:
      V[i+1] = V[i]
      I = i-1
    V[i+1] = X

2. Selection Sort

Complete o código abaixo:

def selection_sort(V):
  for i in range(len(V)):
    minimo = i
    for j in range(i+1, len(V)):
      if V[minimo] > V[j]:
        minimo = j
    temp = V[i]
    V[i] = V[minimo]
    V[minimo] = temp

3. Testando Insertion Sort e Selection Sort

Utilizando as funções insertion_sort e selection_sort com o vetor V = [10, 2, 4, 17, 28, 9]:

V = [10, 2, 4, 17, 28, 9]
insertion_sort(V)
print(V)

V = [10, 2, 4, 17, 28, 9]
selection_sort(V)
print(V)

4. Quick Sort

Identifique o algoritmo e preencha as lacunas:

def quick_sort(L):
  if len(L) <= 1:
    return L
  else:
    left = [X for X in L[1:] if X < L[0]]
    right = [X for X in L[1:] if X >= L[0]]
    return quick_sort(left) + [L[0]] + quick_sort(right)

5. Merge Sort

Preencha as lacunas do algoritmo abaixo:

def merge_sort(arr):
  if len(arr) > 1:
    mid = len(arr) // 2  # Encontrando o meio do array
    L = arr[:mid]  # Dividindo os elementos do array
    R = arr[mid:]  # em 2 metades

    merge_sort(L)  # Ordenando a primeira metade
    merge_sort(R)  # Ordenando a segunda metade

    i = j = k = 0

    while i < len(L) and j < len(R):
      if L[i] < R[j]:
        arr[k] = L[i]
        i += 1
      else:
        arr[k] = R[j]
        j += 1
      k += 1

    while i < len(L):
      arr[k] = L[i]
      i += 1
      k += 1

    while j < len(R):
      arr[k] = R[j]
      j += 1
      k += 1