Algoritmo de ordenação eficiente que usa a estratégia dividir para conquistar, escolhendo um pivô e particionando o array.
O Quick Sort é um algoritmo de ordenação que usa a estratégia dividir para conquistar. Ele escolhe um elemento como pivô e particiona o array em dois subarrays: elementos menores que o pivô e elementos maiores. O processo é recursivo: após particionar, aplica o mesmo procedimento em cada subarray. Quando todos os subarrays têm tamanho 0 ou 1, o array está ordenado. Na prática, o Quick Sort é um dos algoritmos de ordenação mais rápidos, superando o Merge Sort em muitos casos por ter melhor localidade de cache e menor overhead de memória.
“O pivô sempre termina na posição correta após a partição. A cada chamada recursiva, pelo menos um elemento (o pivô) é colocado na posição definitiva.”
Em média, cada partição divide o array pela metade, gerando log n níveis de recursão, cada um processando n elementos.
T(n) = 2T(n/2) + O(n). Pelo Teorema Mestre: O(n log n)
Espaço usado pela pilha de recursão. No caso médio, a profundidade é log n.
Quando o pivô sempre divide o array em duas metades iguais.
Quando o pivô é sempre o menor ou maior elemento (array já ordenado com pivô fixo).
| Algoritmo | Tempo | Espaco | Estavel | Melhor Para |
|---|---|---|---|---|
| Quick Sort(atual) | O(n log n) | O(log n) | Nao | Uso geral, melhor performance média |
| Merge Sort | O(n log n) | O(n) | Sim | Quando estabilidade é necessária |
| Bubble Sort | O(n²) | O(1) | Sim | Fins didáticos |
| Selection Sort | O(n²) | O(1) | Nao | Quando trocas são caras |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def quick_sort(array, low=0, high=None):Definição2 if high is None:3 high = len(array) - 14 5 if low < high:Caso Base6 pivot_index = partition(array, low, high)Partição7 quick_sort(array, low, pivot_index - 1)Chamadas Recursivas8 quick_sort(array, pivot_index + 1, high)Chamadas Recursivas9 10 return array11 12 13def partition(array, low, high):Partição14 pivot = array[high]Pivô15 16 i = low - 117 18 for j in range(low, high):19 if array[j] <= pivot:Comparação20 i += 121 array[i], array[j] = array[j], array[i]Troca22 23 array[i + 1], array[high] = array[high], array[i + 1]Posicionamento do Pivô24 25 return i + 126