Algoritmos de Ordenação (Cheat Sheet)
Uso em projetos e/ou avaliações
Qualquer uso do código abaixo em projetos e/ou avaliações é da responsabilidade do aluno. O código disponível nesta página foi retirado de slides dos docentes, bibliografia da UC ou projetos de outros alunos e adaptado quando necessário.
Algoritmos
Os algoritmos abaixo vão usar as seguintes abstrações (em coerência com os algoritmos disponibilizados pela docência):
typedef int Item; // caso queiramos ordenar inteiros
#define key(A) A
#define less(A, B) (key(A) < key(B))
#define exch(A, B) \
{ \
Item t = A; \
A = B; \
B = t; \
}
#define compexch(A, B) \
if (less(B, A)) \
exch(A, B)Mais ainda, de realçar que todos os algoritmos apresentados nesta secção estão explicados na secção respetiva dos resumos, indicada a par do respetivo código.
Selection Sort
Selection Sort
void selection_sort(Item arr[], int left, int right) {
int i, j;
for (i = left; i < right; i++) {
int min = i;
for (j = i + 1; j <= right; j++) {
if (less(arr[j], arr[min]))
min = j;
}
exch(arr[i], arr[min]);
}
}Insertion Sort
Insertion Sort
void insertion_sort(Item arr[], int left, int right) {
int i, j;
for (i = left + 1; i <= right; i++) {
Item curr = arr[i];
j = i - 1;
while (j >= left && less(curr, arr[j])) {
// vetor percorrido até encontrar o elemento menor que curr
arr[j + 1] = arr[j]; // andamos uma casa para a direita
j--;
}
arr[j + 1] = curr; // guarda o valor na casa acima à do valor menor
}
}Bubble Sort
Bubble Sort
void bubble_sort(Item arr[], int left, int right) {
int i, j;
int done = 0; // flag utilizada para indicar quando o vetor está ordenado
for (i = left; i < right && !done; i++) {
done = 1;
for (j = left; j < right + (left - i); j++) {
if (less(arr[j], arr[j - 1])) {
exch(arr[j - 1], arr[j]);
done = 0;
}
}
}
}Quick Sort
Quick Sort
void quick_sort(Item arr[], int left, int right) {
int i;
if (right <= left)
return;
i = partition(a, left, right);
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
int partition(Item arr[], int left, int right) {
int i = left - 1;
int j = right;
Item el = arr[right];
while (i < j) {
while (less(arr[++i], el));
while (less(el, arr[--j])) {
if (j == left)
break;
if (i < j)
exch(arr[i], arr[j]);
}
exch(arr[i], arr[right]);
}
return i;
}Merge Sort
Merge Sort
void merge_sort(Item arr[], int left, int right) {
int mid = (right + left) / 2;
if (right <= left)
return;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
Item aux[DIM];
void merge(Item arr[], int left, int mid, int right) {
int i, j, k;
for (i = mid + 1; i > left; i--)
aux[i - 1] = arr[i - 1];
for (j = mid; j < right; j++)
aux[right + mid - j] = arr[j + 1];
for (k = left; k <= right; k++) {
// vamos escolhendo os elementos das pontas para ordenar o vetor
if (less(aux[j], aux[i]) || i == mid + 1)
arr[k] = aux[j--];
else
arr[k] = aux[i++];
}
}Heap Sort
Heap Sort
void heap_sort(Item arr[], int left, int right) {
build_heap(arr, left, right);
while (right - left > 0) {
exch(arr[left], arr[right]);
fix_down(arr, left, --right, left);
}
}
void build_heap(Item arr[], int left, int right) {
int k, heapsize = right - left + 1;
for (k = heapsize / 2 - 1; k >= left; k--)
fix_down(arr, left, right, left + k);
}
void fix_down(Item arr[], int left, int right, int k) {
int ileft, iright, largest = k;
ileft = left + left_child(k - left);
iright = left + right_child(k - left);
if (ileft <= right && less(arr[largest], arr[ileft]))
largest = ileft;
if (iright <= right && less(arr[largest], arr[iright]))
largest = iright;
if (largest != k) {
exch(arr[k], arr[largest]);
fix_down(arr, left, right, largest);
}
}
int parent(int k) {
return ((k + 1) / 2) - 1;
}
int left_child(int k) {
return 2 * k + 1;
}
int right_child(int k) {
return 2 * (k + 1);
}Counting Sort
De realçar que a implementação do counting sort varia dependendo da situação: o que é intrínseco à lógica acaba por manter-se, mas temos obviamente que utilizar este algoritmo para ordenar caracteres e inteiros será diferente. A implementação abaixo corresponde a uma implementação-exemplo para ordenação de um vetor de inteiros.
Counting Sort
/* Quantos elementos diferentes podem aparecer */
/* Vamos considerar, neste algoritmo-exemplo, que podem aparecer 9 elementos: os números entre 0 e 8 */
#define DISTINCT_ELEMENTS 9
/* Tamanho máximo do vetor que queremos ordenar */
#define MAX_SIZE 10
void counting_sort(int vec[], int left, int right) {
/* Vetor count que irá guardar quantas vezes aparece cada elemento */
int i, count[DISTINCT_ELEMENTS + 1];
/* Vetor auxiliar onde vamos guardar o vetor ordenado */
/* Mais à frente iremos ver como alocar dinâmicamente
o espaço a ser alocado pelo mesmo (com malloc) */
int sorted_vec[MAX_SIZE];
/* Inicializar vetor count a zeros */
for (i = 0; i < DISTINCT_ELEMENTS; i++) {
count[i] = 0;
}
/* Para cada elemento de vec, somar 1 ao índice correspondente de count */
for (i = left; i < right; i++) {
count[vec[i] + 1]++;
}
/* Para o exemplo da imagem, iremos obter o vetor: */
/* count = [0, 0, 1, 2, 2, 1, 0, 0, 0, 1] */
/* Passar a contagem de elementos para uma contagem comulativa */
for (i = 1; i < DISTINCT_ELEMENTS + 2; i++) {
count[i] += count[i - 1];
}
/* Ficamos agora com um vetor count igual ao da imagem exemplo */
/* Cada índice indica a primeira posição onde iremos inserir o elemento,
daí existir uma posição no início que não está associada a nada. */
/* Para cada elemento do vetor original, vamos ver qual o índice inicial
no vetor ordenado. Para colocarmos corretamente valores repetidos no
vetor ordenado, temos de incrementar o valor no count, de forma a colocar
os repetidos na posição seguinte. */
for (i = left; i < right; i++) {
sorted_vec[count[vec[i]]++] = vec[i];
}
/* O vetor sorted_vec contém agora o resultado final, ordenado */
/* sorted_vec = [1, 2, 2, 3, 3, 4, 8] */
/* Finalmente, inserir o vetor ordenado de volta no vetor original */
for (i = left; i < right; i++) {
vec[i] = sorted_vec[i - left];
}
}
Radix Sort LSD
Radix Sort LSD
/* Estamos a ordenar inteiros */
typedef int Item;
/* Existem 10 dígitos diferentes */
#define DISTINCT_ELEMENTS 10
/* Como exemplo, vamos usar números de 3 dígitos */
#define INT_LENGTH 3
/* Número máximo de elementos a ordenar */
#define MAX_SIZE 100
/* Obter dígito de num no índice digit_i */
int digit(int num, int digit_i) {
while (digit_i > 0) {
num = num / 10;
digit_i--;
}
return num % 10;
}
void radix_lsd(Item vec[], int left, int right) {
int i, curr_digit, count[DISTINCT_ELEMENTS + 1];
int sorted_vec[MAX_SIZE];
for (curr_digit = 0; curr_digit < INT_LENGTH; curr_digit++) {
/* Counting sort em cada dígito */
for (i = 0; i < DISTINCT_ELEMENTS; i++) {
count[i] = 0;
}
for (i = left; i < right; i++) {
count[digit(vec[i], curr_digit) + 1]++;
}
for (i = 1; i < DISTINCT_ELEMENTS + 2; i++) {
count[i] += count[i - 1];
}
for (i = left; i < right; i++) {
sorted_vec[count[digit(vec[i], curr_digit)]++] = vec[i];
}
for (i = left; i < right; i++) {
vec[i] = sorted_vec[i - left];
}
}
}Radix Sort MSD
Radix Sort MSD
void radix_msd(int a[], int l, int r, int w) {
int i = l, j = r;
if (r <= l || w > bitsword) {
return;
}
while (j != i) {
while (digit(a[i], w) == 0 && (i < j)) {
i++;
}
while (digit(a[j], w) == 1 && (j > i)) {
j--;
}
exch(a[i], a[j]);
}
if (digit(a[r], w) == 0) {
j++;
}
radix_msd(a, l, j - 1, w + 1);
radix_msd(a, j, r, w + 1);
}Quando reparas que o Bogosort é o único algoritmo que consegue ordenar à primeira
