Teorica_Ordenacao_Recursiva

Algoritmos de ordenação
Ordenação rápida (“Quicksort”)
➔ Baseia-se num princípio muito simples que, quando aplicado recursivamente, acaba por ordenar o vector.
➔ Este princípio é composto por 2 passos essenciais:
1. Escolher um elemento do vector, o pivot (por ex., V[0]);
2. Dividir o vector em 2 partes (esquerda e direita), em que:
✔ Parte esquerda com os elementos menores do que o pivot;
✔ Parte direita com os elementos maiores do que o pivot.
➔ Ao ser aplicado succesivamente este princípio a ambas as partes, quando o processo recursivo terminar o vector está ordenado.

Algoritmos de ordenação
Ordenação rápida (“Quicksort”)
O algoritmo é composto então por 3 passos:
1. Determinar a posição final k do elemento pivot (V[0]) no vector e colocá-lo nessa posição, dividindo o vector em 2 partes:
✔ Esquerda = V[0], ..., V[k-1]
✔ Direita = V[k+1], ..., V[tam-1]
2. Aplicar o algoritmo recursivamente à parte esquerda;
3. Aplicar o algoritmo recursivamente à parte direita.

Algoritmos de ordenação
Quicksort (Algoritmo)
Ordenar por Quicksort um subvector de V desde inicio até fim
Se (inicio < fim) então k ← posição final do pivot, V[inicio], no vector
Ordenar por Quicksort o subvector esquerdo ao pivot
Ordenar por Quicksort o subvector direito ao pivot
Note-se que se (inicio >= fim) então o subvector de V tem apenas um elemento (inicio = fim) ou está vazio (inicio > fim). Logo, este subvector está ordenado.

Algoritmos de ordenação
Quicksort (Algoritmo)
Determinar a posição final k do pivot (V[inicio]) no subvector de V desde inicio até fim k ← inicio
Para i desde (inicio+1) até fim fazer
Se (V[i] < V[inicio]) então k←k+1 Trocar (V[k], V[i])
Trocar (V[k], V[inicio])
Devolver (k)

Algoritmos de ordenação
Quicksort (função C) void Trocar (int *a, int *b)
{
int aux; aux = *a;
*a = *b;
*b = aux;
}

Algoritmos de ordenação
Quicksort (função C) int DeterminarPivot (int V[], int inicio, int fim)
{
int i, k = inicio;