Sortings - C

Quick Sort
Algoritmo – Pseudocódigo:
QuickSort(‘vetor’ de inteiros, inteiro ‘inicio’, inteiro ‘fim’):
{
Inteiro Meio
Se fim > inicio
{
Meio  separa(vetor, inicio, fim) quickSort(vetor, inicio, R-1) quickSort(vetor, R+1, fim)
}
}

Análise de Complexidade – Big-oh:
1- declaração de Meio
1- checagem
1- atribuição de Meio n- função separa
F(n/2)- chamada recursiva
F(n/2)- chamada recursiva
TOTAL: 3 + n + T(i-1) + T(n-i)
No melhor caso, quando pivô está sempre no meio:
|T(n) = 2T(n/2) + n + 3 n>1 |T(n) = 1 n≤1 T(n) = 2(2T(n/4) + n/2) + n/2
= 4T(n/4) + 2n + 6
= 8T(n/8) + 3n + 9
(...)
=2iT(n/2i) + in + 3i

Substituindo i = log2n:
=2lognT(n/2logn) + nlogn + 3logn
=2T(1) + nlogn + 3logn
Portanto: T(n) € O(nlogn)

 melhor caso.

No pior caso, quando pivô está sempre na primeira ou última posição:
|T(n) = T(n-1) + n + 3 n>1 |T(n) = 1 n≤1 T(n) = T(n – 2) + 3 + n + (n – 1)
T(n – 3) + 3 + n + (n – 1) + (n – 2)
(...)
T(1) + 3 + n + (n-1) + (......)
Tem-se:
𝑛

∑ i = n(n + 1)/2
𝑖=1

Portanto: T(n) € O(n2)

 pior caso.

Counting Sort
Algoritmo – Pseudocódigo:
CountingSort(‘vetor’ de inteiros, inteiro ‘tamanho’):
{
Inteiro i, vetor_auxiliar, vetor_ordenado
Inteiro mínimo  menor(vetor, tamanho)
Inteiro máximo maior(vetor, tamanho)
Aloca vetor_auxiliar[maior-menor+1]
Aloca vetor_ordenado[tamanho]
Para i=0 e enquanto i < tamanho vetor_auxiliar[vetor[i]-minimo]++ i++
Para i=1 e enquanto i ≤ maximo-minimo vetor_auxiliar[i]+ vetor_auxiliar[i-1] i++ Para i=tamanho-1 e enquanto i ≥ 0 vetor_ordenado[--vetor_auxiliar[vetor[i]-minimo]]  vetor[i] i++ Para i=0 e enquanto i < tamanho vetor[i]  vetor_ordenado[i] i++ libera(vetor_auxiliar, vetor_ordenado)
}

Análise de Complexidade – Big-oh:
5- declaração de i, vetores, mínimo e maximo
2- atribuição de mínimo e maximo
2- alocação de vetores
4(3n+2)- quatro “for” com operação
2- libera vetores
TOTAL: 5 + 2 + 2 + 4(3n+2) + 2 = 12n + 19
Portanto: T(n) €