Quick Sort
Última atualização
Quicksort é um algoritmo de dividir para conquistar que ordena em torno de um "pivô". Ele escolhe um elemento pivô e então particiona o array de modo que tudo o que é menor venha antes e tudo o que é maior venha depois, o que fixa o pivô em sua posição final ordenada. Em seguida, recorre sobre as partições esquerda e direita. Esta visualização usa o esquema de Lomuto com o último elemento como pivô. Pressione reproduzir para ver a partição e a colocação do pivô.
Quicksort costuma ser a ordenação de propósito geral mais rápida na prática graças ao bom comportamento de cache e à partição no próprio local, com média de O(n log n). Seu pior caso é O(n²) (por exemplo, um array já ordenado com uma escolha ruim de pivô), que estratégias de pivô como mediana de três ou aleatorização evitam.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Melhor caso | O(n log n) | Partições equilibradas |
| Caso médio | O(n log n) | Ordem aleatória |
| Pior caso | O(n²) | Pivôs desequilibrados de forma consistente |
| Espaço | O(log n) | Pilha de recursão (partição no próprio local) |
| Estável | Não | As trocas da partição reordenam elementos iguais |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Escolha um pivô (aqui, o último elemento do intervalo). |
| 2 | Partição: mova para a esquerda dele todos os elementos menores que o pivô. |
| 3 | Troque o pivô para a fronteira: agora ele está na posição final. |
| 4 | Aplique quicksort recursivamente na partição esquerda. |
| 5 | Aplique quicksort recursivamente na partição direita. |
Exemplo resolvido
Ordenando [5, 2, 4, 1] com o esquema de Lomuto (último elemento como pivô):
| Passagem | Array | Ação |
|---|---|---|
| Início | [5, 2, 4, 1] | Particiona todo o intervalo; o pivô é 1 (último elemento). |
| 1 | [1, 2, 4, 5] | Nada é menor que 1, então troca 1 para o índice 0; o pivô 1 fica final. Recorre à direita sobre [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Particiona [2, 4, 5] com pivô 5; tanto 2 quanto 4 são menores, então 5 permanece no fim e fica final. Recorre à esquerda sobre [2, 4]. |
| 3 | [1, 2, 4, 5] | Particiona [2, 4] com pivô 4; 2 é menor, então 4 permanece no lugar e fica final. 2 é um único elemento, então já está ordenado. |
| Fim | [1, 2, 4, 5] | Cada pivô fica fixado em seu lugar; o array está ordenado. |
Quando usar quicksort
| Use quando | Evite quando |
|---|---|
| Você precisa de uma ordenação em memória rápida e de propósito geral com constantes pequenas. | Você precisa de tempo garantido O(n log n) no pior caso (use heap sort ou merge sort). |
A memória é escassa: a partição é no próprio local e precisa apenas de O(log n) de pilha. | Você precisa de uma ordenação estável que preserve a ordem das chaves iguais. |
| Os dados estão em ordem aleatória ou desconhecida e você usa um pivô aleatório ou mediana de três. | A entrada já está ordenada ou quase ordenada e o pivô é fixo, disparando O(n²). |
| A localidade de cache importa, já que o quicksort acessa a memória sequencialmente. | Você ordena uma lista encadeada, onde o merge sort evita o acesso aleatório do qual o quicksort depende. |
Código de Quick Sort
Uma implementação limpa e executável de Quick Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Quick Sort em Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Código de Quick Sort em JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Código de Quick Sort em Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Código de Quick Sort em C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Código de Quick Sort em C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Perguntas frequentes sobre Quick Sort
Qual é a complexidade de tempo do quicksort?
Quicksort tem média
O(n log n) e é O(n log n) no melhor caso, mas degrada para O(n²) no pior caso quando as partições ficam consistentemente desequilibradas. Pivôs aleatórios ou de mediana de três tornam o pior caso muito improvável.Quicksort é estável?
Não. A partição padrão no próprio local troca elementos distantes, o que pode mudar a ordem relativa de chaves iguais. Existem variantes estáveis, mas elas abrem mão da vantagem do quicksort de operar no próprio local.
Por que o quicksort costuma ser mais rápido que o merge sort?
Quicksort particiona no próprio local com excelente localidade de cache e sem buffer adicional, então suas constantes são pequenas. Merge sort iguala seu limite
O(n log n), mas paga por um buffer O(n) e mais movimentação de dados.Quicksort vs merge sort: qual devo usar?
Escolha quicksort para ordenar arrays em memória de forma rápida e no próprio local, onde suas constantes pequenas geralmente vencem. Escolha merge sort quando precisar de uma ordenação estável, garantia de pior caso
O(n log n), ou quando ordenar listas encadeadas ou dados externos que não cabem na RAM.Por que o quicksort se torna O(n²) em um array ordenado?
Com um pivô fixo como o primeiro ou último elemento, uma entrada já ordenada faz cada partição separar apenas um elemento, produzindo
n níveis de recursão em vez de log n. Escolher o pivô aleatoriamente ou com mediana de três quebra esse padrão e restaura o comportamento O(n log n).Qual é a diferença entre os esquemas de partição de Lomuto e Hoare?
O esquema de Lomuto usa um único índice que varre da esquerda para a direita e é mais simples de codificar, por isso esta visualização o usa. O esquema de Hoare usa dois ponteiros que avançam para o interior e costuma fazer menos trocas, sendo mais rápido na prática, mas não coloca o pivô em sua posição final durante o passo de partição.
Recursos relacionados
Mais visualizações
