1. Conceito do Algoritmo

Quick Sort é um algoritmo de ordenação baseado no paradigma de divisão e conquista, proposto por Tony Hoare em 1959. O princípio fundamental é dividir um problema complexo em subproblemas menores e independentes, resolvê-los recursivamente e combinar os resultados.

Passos do Algoritmo

1. Escolha do Pivô: Seleciona-se um elemento como referência (pivô) no array. Estratégias comuns incluem o primeiro, último ou um elemento aleatório.
2. Particionamento: Reorganiza-se o array de modo que elementos menores que o pivô fiquem à esquerda e os maiores à direita. Após isso, o pivô está em sua posição final correta, diviidndo o array em duas metades.
3. Recursão: Aplica-se o mesmo processo às subarrays esquerda e direita até que todas tenham tamanho 0 ou 1, resultando em um array ordenado.

Exemplo

Considere o array arr = [5, 3, 8, 6, 7, 2]. Usando Quick Sort:

• Escolha o pivô 5.
• Após particionamento: [3, 2, 5, 8, 6, 7] (pivô 5 na posição correta).
• Recursivamente ordene [3, 2] para [2, 3] e [8, 6, 7] para [6, 7, 8].
• Resultado final: [2, 3, 5, 6, 7, 8].

Complexidade

• Tempo médio: \(O(n \log n)\), devido à divisão equilibrada das subarrays.
• Pior caso: \(O(n^2)\), quando o pivô é escolhido de forma desfavorável (ex.: sempre o menor ou maior elemento).
• Espaço: \(O(\log n)\) em média, devido à profundidade da recursão; pode chegar a \(O(n)\) no pior caso.

2. Exemplos de Aplicação

2.1 Classificação de Cores

Problema: Dado um array contendo 0, 1 e 2, ordene-o in-place. Utiliza-se uma abordagem de três ponteiros para varredura única, com compleixdade O(n) tempo e O(1) espaço.

• Ponteiros: esq marca o final dos 0s (inicia em -1), dir marca o início dos 2s (inicia em n), e idx percorre o array.
• Lógica: Se elemento for 0, troque com esq avance ambos; se for 1, avance idx; se for 2, troque com dir e recue dir.

void classificarCores(vector<int>& itens) {
    int tamanho = itens.size();
    int esq = -1, dir = tamanho, idx = 0;
    while (idx < dir) {
        if (itens[idx] == 0) {
            swap(itens[++esq], itens[idx++]);
        } else if (itens[idx] == 1) {
            ++idx;
        } else {
            swap(itens[--dir], itens[idx]);
        }
    }
}

2.2 Ordenação de Array

Problema: Ordene um array usando Quick Sort otimizado com seleção aleatória de pivô para evitar o pior caso. Implementa-se particionamento de três vias para lidar com elementos duplicados.

• Estrutura: Função principal ordenarArray invoca ordenaRapida, que usa obterAleatorio para escolher pivô.
• Particionamento: Três regiões: menores que pivô (esquerda), iguais (meio), maiores (direita). Ponteiros menor, maior e atual controlam a divisão.

vector<int> ordenarArray(vector<int>& dados) {
    srand(time(NULL));
    int inicio = 0, fim = dados.size() - 1;
    ordenaRapida(dados, inicio, fim);
    return dados;
}

void ordenaRapida(vector<int>& arr, int ini, int fim) {
    if (ini >= fim) return;
    int pivo = obterAleatorio(arr, ini, fim);
    int menor = ini - 1, maior = fim + 1;
    int i = ini;
    while (i < maior) {
        if (arr[i] < pivo) {
            swap(arr[++menor], arr[i++]);
        } else if (arr[i] == pivo) {
            ++i;
        } else {
            swap(arr[--maior], arr[i]);
        }
    }
    ordenaRapida(arr, ini, menor);
    ordenaRapida(arr, maior, fim);
}

int obterAleatorio(vector<int>& arr, int ini, int fim) {
    return arr[(rand() % (fim - ini + 1)) + ini];
}

2.3 K-ésimo Maior Elemento

Problema: Encontre o k-ésimo maior elemento sem ordenar completamente o array. Utiliza-se Quick Sort com particionamento para direcionnar a busca apenas à região relevante.

• Abordagem: Escolha pivô aleatório, particione em três partes e compare o tamanho das regiões com k para decidir onde buscar recursivamente.
• Lógica de busca: Calcule o comprimento das regiões maior e igual ao pivô. Se k estiver na região maior, busque lá; se na igual, retorne o pivô; senão, ajuste k e busque na região menor.

int encontrarKesimoMaior(vector<int>& numeros, int k) {
    srand(time(NULL));
    int ini = 0, fim = numeros.size() - 1;
    return ordenaParcial(numeros, ini, fim, k);
}

int ordenaParcial(vector<int>& arr, int ini, int fim, int k) {
    if (ini >= fim) return arr[ini];
    int pivo = obterAleatorio(arr, ini, fim);
    int menor = ini - 1, maior = fim + 1;
    int i = ini;
    while (i < maior) {
        if (arr[i] < pivo) {
            swap(arr[++menor], arr[i++]);
        } else if (arr[i] == pivo) {
            ++i;
        } else {
            swap(arr[--maior], arr[i]);
        }
    }
    int tamMaior = fim - maior + 1;
    int tamIgual = maior - menor - 1;
    if (k <= tamMaior) {
        return ordenaParcial(arr, maior, fim, k);
    } else if (k <= tamMaior + tamIgual) {
        return pivo;
    } else {
        return ordenaParcial(arr, ini, menor, k - tamMaior - tamIgual);
    }
}

int obterAleatorio(vector<int>& arr, int ini, int fim) {
    return arr[(rand() % (fim - ini + 1)) + ini];
}

2.4 Gerenciamento de Inventário

Problema: Extraia os menores cnt elementos de um array sem ordená-lo totalmente. Aplica-se Quick Sort com particionamento para isolar a região de interesse.

• Objetivo: Após particionamento, determine se os cnt elementos estão totalmente à esquerda, incluem a região do pivô, ou requerem elementos da direita.
• Recursão direcionada: Compare cnt com o tamanho das regiões menor e igual ao pivô para decidir a recursão adequada.

vector<int> gerenciarInventario(vector<int>& estoque, int cnt) {
    srand(time(NULL));
    int ini = 0, fim = estoque.size() - 1;
    ordenarMenores(estoque, ini, fim, cnt);
    vector<int> resultado;
    for (int i = 0; i < cnt; ++i) {
        resultado.push_back(estoque[i]);
    }
    return resultado;
}

void ordenarMenores(vector<int>& arr, int ini, int fim, int cnt) {
    if (ini >= fim) return;
    int pivo = obterAleatorio(arr, ini, fim);
    int menor = ini - 1, maior = fim + 1;
    int i = ini;
    while (i < maior) {
        if (arr[i] < pivo) {
            swap(arr[++menor], arr[i++]);
        } else if (arr[i] == pivo) {
            ++i;
        } else {
            swap(arr[--maior], arr[i]);
        }
    }
    int tamMenor = menor - ini + 1;
    int tamIgual = maior - menor - 1;
    if (cnt < tamMenor) {
        ordenarMenores(arr, ini, menor, cnt);
    } else if (cnt <= tamMenor + tamIgual) {
        return;
    } else {
        ordenarMenores(arr, maior, fim, cnt - tamMenor - tamIgual);
    }
}

int obterAleatorio(vector<int>& arr, int ini, int fim) {
    return arr[(rand() % (fim - ini + 1)) + ini];
}