Quick Sort

Conceito

Quick sort também divide para conquistar, mas invertendo onde o trabalho acontece: em vez de dividir barato e juntar caro (como o 2. Merge Sort), ele divide caro e junta de graça.

O particionamento é o algoritmo. Escolhe um pivô e reorganiza o array de modo que tudo menor que o pivô fique à esquerda e tudo maior à direita. Depois disso:

• o pivô está na posição final — nunca mais precisa se mover
• as duas partes podem ser ordenadas independentemente, e nada precisa ser intercalado depois

Por isso não há buffer: o trabalho é feito na descida, in-place.

O pior caso é O(n²), e a causa é sempre a mesma: partições desbalanceadas. Se o pivô é sempre o mínimo (ou o máximo), você obtém partições de tamanho 0 e n−1 → n níveis de recursão, cada um com O(n) de particionamento.

Mitigações, em ordem de custo:

Por que é o padrão apesar do pior caso:

1. constante pequena — o laço de particionamento é simples e previsível
2. in-place — O(log n) de pilha, não O(n) de buffer
3. localidade de cache excelente — particionar é varredura sequencial

Os pontos 1 e 3 é que fazem a diferença real. Na memória, quick sort vence merge sort por uma margem que a notação O não mostra.

Ninguém usa quick sort puro hoje. As implementações reais são híbridas:

• introsort — quicksort, com heapsort quando a profundidade excede ~2·log n
• pdqsort (pattern-defeating quicksort) — detecta padrões (já ordenado, muitas duplicatas, reverso) e adapta a estratégia
• e todas caem para insertion sort em partições pequenas (< ~12 elementos), onde ele é imbatível

Em Go

slices.Sort usa pdqsort desde o Go 1.19. Isso significa que, em Go, o pior caso de "quick sort" é O(n log n) garantido — pdqsort detecta a degeneração e troca de estratégia.

O que o pdqsort faz concretamente:

• detecta sequências já ordenadas e sai em O(n)
• detecta muitas duplicatas e usa particionamento em três vias (menores, iguais, maiores), evitando o caso patológico do "tudo igual"
• limita a profundidade da recursão e cai para heapsort quando estoura
• insertion sort em partições pequenas

Ele é instável: se você precisa de estabilidade, slices.SortStableFunc (2. Merge Sort).

Uma diferença medível de API: sort.Slice usa reflexão para trocar elementos; slices.Sort e slices.SortFunc usam generics e geram código específico. A diferença é grande o suficiente para importar em código quente — em código novo, não há motivo para usar sort.Slice.

Respostas às perguntas-guia

1. O que o particionamento faz, e por que ele é o coração do algoritmo?

Conceito: reorganiza o array em torno do pivô e coloca o pivô na posição final. É o coração porque, feito ele, não há nada a juntar depois — é o que dispensa o buffer.

Em Go: pdqsort usa particionamento em três vias quando detecta duplicatas, o que transforma o pior caso do "array com poucos valores distintos" em linear.

2. Por que o pior caso é O(n²), e que escolha de pivô provoca isso?

Conceito: partições desbalanceadas dão n níveis em vez de log n. A escolha do primeiro elemento com entrada ordenada é o gatilho clássico.

Em Go: não acontece com slices.Sort — o pdqsort detecta exatamente esse padrão. Se você escreve o seu, acontece.

3. Se o pior caso é pior que o merge sort, por que ele é o padrão em tanta biblioteca?

Conceito: constante pequena, in-place, e localidade de cache. E porque os híbridos modernos eliminaram o pior caso.

Em Go: mais um motivo — sem buffer significa sem alocação, e alocação é pressão de GC. slices.Sort não aloca.

4. O que sua linguagem realmente usa no sort da stdlib?

Em Go: pdqsort para slices.Sort / sort.Sort (desde 1.19); antes disso era um introsort caseiro (quicksort + shellsort + heapsort). Para o estável, insertion sort + symmerge in-place. Vale abrir src/sort/zsortfunc.go uma vez: o código é comentado e explica cada heurística.

Trade-offs

Do conceito:

• In-place e cache-friendly, em troca de um pior caso quadrático que exige mitigação.
• Instável, em troca de velocidade.
• A escolha do pivô é onde você troca garantia por velocidade média: aleatório é rápido e probabilístico; mediana de medianas é garantido e lento.

Em Go:

• pdqsort te dá o melhor dos dois: rápido no caso comum, O(n log n) garantido no pior. O custo é complexidade de implementação — que você não paga, a stdlib paga.
• slices.Sort (generics) vs sort.Slice (reflexão): mesma tarefa, custos diferentes.
• Instável por padrão significa que ordenação por múltiplas chaves em passadas silenciosamente não funciona. Não há erro; a ordem simplesmente se perde.

Exemplo prático

package main

import (
	"fmt"
	"math/rand"
	"slices"
	"time"
)

// Particionamento de Lomuto: o coração do algoritmo
func particiona(s []int, lo, hi int) int {
	pivo := s[hi]
	i := lo
	for j := lo; j < hi; j++ {
		if s[j] < pivo {
			s[i], s[j] = s[j], s[i]
			i++
		}
	}
	s[i], s[hi] = s[hi], s[i] // pivô vai para a posição FINAL
	return i
}

// Quick sort ingênuo: pivô = último elemento
func quickIngenuo(s []int, lo, hi int, prof *int, nivel int) {
	if nivel > *prof {
		*prof = nivel
	}
	if lo >= hi {
		return
	}
	p := particiona(s, lo, hi)
	quickIngenuo(s, lo, p-1, prof, nivel+1)
	quickIngenuo(s, p+1, hi, prof, nivel+1)
}

// Mesma coisa com pivô ALEATÓRIO: mata o pior caso na prática
func quickAleatorio(s []int, lo, hi int, prof *int, nivel int) {
	if nivel > *prof {
		*prof = nivel
	}
	if lo >= hi {
		return
	}
	r := lo + rand.Intn(hi-lo+1)
	s[r], s[hi] = s[hi], s[r] // sorteia e joga para a posição de pivô
	p := particiona(s, lo, hi)
	quickAleatorio(s, lo, p-1, prof, nivel+1)
	quickAleatorio(s, p+1, hi, prof, nivel+1)
}

func main() {
	const n = 2000

	// entrada JÁ ORDENADA: o pior caso do pivô ingênuo
	ordenada := make([]int, n)
	for i := range ordenada {
		ordenada[i] = i
	}

	a := slices.Clone(ordenada)
	prof := 0
	t := time.Now()
	quickIngenuo(a, 0, len(a)-1, &prof, 1)
	fmt.Printf("ingênuo  sobre ordenada: profundidade=%-6d tempo=%v\n", prof, time.Since(t).Round(time.Microsecond))

	b := slices.Clone(ordenada)
	prof = 0
	t = time.Now()
	quickAleatorio(b, 0, len(b)-1, &prof, 1)
	fmt.Printf("aleatório sobre ordenada: profundidade=%-6d tempo=%v\n", prof, time.Since(t).Round(time.Microsecond))

	c := slices.Clone(ordenada)
	t = time.Now()
	slices.Sort(c) // pdqsort: detecta que já está ordenado
	fmt.Printf("slices.Sort (pdqsort):    %v  <- detecta o padrão\n", time.Since(t).Round(time.Microsecond))

	fmt.Println("todos ordenados corretamente?",
		slices.IsSorted(a) && slices.IsSorted(b) && slices.IsSorted(c))

	// instável: a ordem relativa de iguais NÃO é preservada
	type P struct{ K, Ordem int }
	ps := []P{{1, 0}, {1, 1}, {1, 2}, {0, 3}}
	slices.SortFunc(ps, func(x, y P) int { return x.K - y.K })
	fmt.Println("instável, iguais em ordem arbitrária:", ps)
}

profundidade é a métrica que expõe o problema: com pivô ingênuo sobre entrada ordenada, ela é ~n (recursão degenerada); com pivô aleatório, ~log n.

Relacionado

• 2. Merge Sort — a troca oposta: memória por garantia e estabilidade
• 1. Busca Binária — o mesmo descarte pela metade, sem reorganizar
• 5. Recursão — semana 3, profundidade de recursão como métrica de saúde
• 1. Notação Big-O — semana 2, por que pior caso e caso médio divergem aqui

---

Parte de Semana 04 - Algoritmos Essenciais · 00 - MOC Fundamentos de Programação