Ordenação Rápida

9.1 Definição da Ordenação Rápida

Ordenação Rápida (Quick Sort) é um algoritmo de ordenação eficiente que utiliza a abordagem "dividir e conquistar". Ele funciona escolhendo um elemento pivô, dividindo o array em dois subarrays — elementos menores que o pivô e elementos maiores que o pivô — e então aplicando recursivamente o mesmo processo a cada subarray.

O Quick Sort surgiu como uma tentativa de resolver a questão de "como mover rapidamente os elementos menores para a esquerda e os maiores para a direita". Suponha que temos o menor elemento à direita, é possível movê-lo rapidamente, se não para sua posição final, pelo menos próximo dela? Isso reduziria significativamente o número de comparações desnecessárias.

Princípio de funcionamento:

1. Escolha do pivô:

Escolhemos um elemento do array como pivô. Pode ser o primeiro, o último, o elemento médio ou um elemento aleatório. Às vezes, é a média de três elementos aleatórios.

2. Particionamento:

Movemos todos os elementos menores que o pivô para a esquerda do array, e todos os elementos maiores que o pivô para a direita. Como resultado, o pivô fica na sua posição final no array ordenado.

3. Aplicação recursiva:

Aplicamos o processo recursivamente aos subarrays esquerdo e direito, sem incluir o pivô.

Processo passo a passo

1. Escolhemos o pivô.
2. Movemos os elementos menores que o pivô para a esquerda e os elementos maiores para a direita.
3. Aplicamos o processo recursivamente aos subarrays.

Complexidade de tempo e espaço do Quick Sort

Complexidade de tempo:

• No pior caso: O(n^2) — ocorre quando sempre é escolhido o pior pivô (por exemplo, quando o array já está ordenado).
• Em média: O(n log n) — para dados distribuídos aleatoriamente.
• No melhor caso: O(n log n) — quando o array é sempre dividido em partes iguais.

Complexidade de espaço:

O(log n) — necessário para armazenar a pilha de chamadas recursivas, se a recursão de cauda é usada e os pivôs são escolhidos adequadamente.

9.2 Implementação do algoritmo Quick Sort

Implementação em Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Caso base: array com 0 ou 1 elemento já está ordenado
    
    pivot = arr[len(arr) // 2]  # Escolhemos o pivô
    left = [x for x in arr if x < pivot]  # Elementos menores que o pivô
    middle = [x for x in arr if x == pivot]  # Elementos iguais ao pivô
    right = [x for x in arr if x > pivot]  # Elementos maiores que o pivô
    
    return quick_sort(left) + middle + quick_sort(right)

# Exemplo de uso:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Array ordenado:", sorted_arr)
# Saída: Array ordenado: [1, 1, 2, 3, 6, 8, 10]

Exemplo de funcionamento do algoritmo

Consideremos o array: [3, 6, 8, 10, 1, 2, 1]

Primeira passagem:

• Pivô: 8
• Elementos à esquerda: [3, 6, 1, 2, 1]
• Elementos no meio: [8]
• Elementos à direita: [10]

Ordenação recursiva da parte esquerda [3, 6, 1, 2, 1]:

• Pivô: 1
• Elementos à esquerda: []
• Elementos no meio: [1, 1]
• Elementos à direita: [3, 6, 2]

Ordenação recursiva da parte direita [3, 6, 2]:

• Pivô: 6
• Elementos à esquerda: [3, 2]
• Elementos no meio: [6]
• Elementos à direita: []

Ordenação recursiva da parte esquerda [3, 2]:

• Pivô: 2
• Elementos à esquerda: []
• Elementos no meio: [2]
• Elementos à direita: [3]

Resultado da fusão: [1, 1, 2, 3, 6] para a parte esquerda, [10] para a parte direita, e [8] para o meio.

Array final ordenado: [1, 1, 2, 3, 6, 8, 10]