• Implemente uma função que utilize Quicksort até que o tamanho do subvetor seja menor que 10, e então use Insertion Sort para ordenar esses pequenos subvetores.
    Compare o tempo de execução com a versão padrão do Quicksort.

Passo 1

Vamos resolver um exercício que envolve algoritmos de ordenação, especificamente o Quicksort e o Insertion Sort. A tarefa é implementar uma função que usa Quicksort para ordenar um vetor, mas quando o tamanho de um subvetor fica menor que 10 elementos, usa o Insertion Sort para ordenar esse subvetor menor. Além disso, precisamos comparar o tempo de execução dessa implementação com a versão padrão do Quicksort. Para isso, vamos precisar entender como funcionam ambos os algoritmos e como implementar uma versão híbrida que combina os dois.

Passo 2

Primeiro, vamos entender o Quicksort. Ele é um algoritmo de ordenação eficiente que segue a estratégia “dividir para conquistar”. A ideia principal é:
  1. Escolher um “pivô”: Um elemento do vetor que vai ajudar a dividir o vetor em partes menores.
  2. Particionar o vetor: Reorganizar os elementos de tal forma que todos os elementos menores que o pivô fiquem à esquerda e os maiores à direita.
  3. Recursivamente aplicar Quicksort nas subpartes esquerda e direita até que todo o vetor esteja ordenado.
Vamos implementar uma função básica de Quicksort em Python:
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Escolhendo o pivô como o elemento do meio
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Passo 3

Agora, vamos falar sobre o Insertion Sort. Este é um algoritmo simples e eficiente para ordenar pequenos vetores. Ele funciona de forma semelhante à maneira como organizamos cartas na mão: pegamos um elemento e o inserimos na posição correta em relação aos já ordenados. Os passos básicos são:
  1. Percorrer o vetor do segundo elemento ao último.
  2. Para cada elemento, compará-lo com os anteriores e trocá-lo de posição até que esteja no lugar certo.
Aqui está uma implementação em Python:
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move os elementos de arr[0..i-1], que são maiores que a chave, para uma posição à frente
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Passo 4

O próximo passo é combinar Quicksort e Insertion Sort. A ideia é usar Quicksort para dividir o vetor até que os subvetores tenham menos de 10 elementos. Quando isso acontecer, usamos o Insertion Sort para ordenar esses pequenos subvetores, já que o Insertion Sort é mais eficiente para tamanhos pequenos.
Vamos modificar a função de Quicksort para incluir essa lógica:
def hybrid_sort(arr, threshold=10):
    if len(arr) <= threshold:
        return insertion_sort(arr)
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return hybrid_sort(left, threshold) + middle + hybrid_sort(right, threshold)

Passo 5

Finalmente, vamos comparar o tempo de execução entre a versão padrão do Quicksort e nossa versão híbrida que usa Insertion Sort para subvetores pequenos. Para isso, usaremos a biblioteca time do Python para medir o tempo.
Aqui está como podemos fazer isso:
import time
import random

# Gerando uma lista aleatória de 10000 elementos
data = random.sample(range(100000), 10000)

# Medindo o tempo do Quicksort padrão
start_time = time.time()
sorted_quicksort = quicksort(data.copy())
quicksort_time = time.time() - start_time

# Medindo o tempo do Quicksort híbrido
start_time = time.time()
sorted_hybrid = hybrid_sort(data.copy())
hybrid_time = time.time() - start_time

print(f"Tempo do Quicksort padrão: {quicksort_time:.4f} segundos")
print(f"Tempo do Quicksort híbrido: {hybrid_time:.4f} segundos")

Resposta

Ao executar o código acima, você verá uma comparação clara dos tempos de execução entre o Quicksort padrão e o Quicksort híbrido que utiliza Insertion Sort para subvetores menores que 10 elementos. Geralmente, a versão híbrida tende a ser mais rápida ou comparável ao Quicksort padrão, especialmente em casos onde muitos subvetores pequenos são criados, aproveitando a eficiência do Insertion Sort nesses cenários.

Exercícios relacionados