Please enable JavaScript.
Coggle requires JavaScript to display documents.
ORDENAÇÃO, for j = 0 … n-2-i, if A[j+1] < A[j] then swap A[j], A[j+1],…
ORDENAÇÃO
Força Bruta / Busca Exaustiva
Selection Sort
Método: em cada iteração, encontra o menor elemento do subvetor não ordenado e troca com o elemento na posição corrente.
Pseudocódigo:
for i = 0 … n-2
Complexidade: Θ(n²) comparações; Θ(n) trocas
Bubble Sort
Método: varre repetidamente o vetor, comparando e trocando pares adjacentes fora de ordem, “borbulhando” o maior elemento até o fim.
Pseudocódigo:
for i = 0 … n-2
Complexidade: Θ(n²) comparações no pior caso; trocas dependem da desordem
Decrease-and-Conquer (Diminuição-por-um)
Insertion Sort
Método: considera o prefixo A[0..i-1] já ordenado e insere A[i] na posição correta, deslocando elementos maiores para a direita.
Pseudocódigo:
for i = 1 … n-1
Complexidade:
Melhor caso (vetor já ordenado): Θ(n)
Pior caso (vetor em ordem decrescente): Θ(n²)
Caso médio: ≈ n²/4 comparações
Divide-and-Conquer (Dividir-e-Conquistar)
Merge Sort
Método: divide o vetor em duas metades, ordena recursivamente cada metade e faz o merge em um vetor auxiliar.
Pseudocódigo:
Mergesort(A[0..n-1]):
Complexidade: Θ(n log n) no pior e caso médio; requer O(n) espaço extra
for j = 0 … n-2-i
if A[j+1] < A[j] then swap A[j], A[j+1]
v ← A[i]; j ← i-1
while j ≥ 0 and A[j] > v do
A[j+1] ← A[j]; j ← j-1
A[j+1] ← v
if n > 1 then
B ← A[0..⌊n/2⌋-1]; C ← A[⌊n/2⌋..n-1]
Mergesort(B); Mergesort(C)
Merge(B, C, A)
min ← i
for j = i+1 … n-1
if A[j] < A[min] then min ← j
swap A[i], A[min]