Uma implementação do HeapSort
Publicado por Felipe Martins dos Santos (última atualização em 30/06/2010)
[ Hits: 22.719 ]
Homepage: https://felipemartinsss.vercel.app/
Este código em ANSI-C fornece a implementação do algoritmo de ordenação HeapSort. O algoritmo recebe esse nome por utilizar uma estrutura de dados chamada Heap. Existem MaxHeaps (elemento máximo na raiz) e MinHeaps (elemento mínimo na raiz).
Na implementação fornecida de HeapSort é utilizado um MaxHeap e a cada iteração o elemento máximo é extraído do Heap e inserido no final de um vetor, até que o vetor contenha todos os números que estavam no Heap, mas em ordem não decrescente.
Para compilar, utilize o comando:
gcc -ansi -pedantic -Wall HeapSort.c -o HeapSort
Para executar:
./HeapSort
#include <stdio.h> #include <stdlib.h> #include <time.h> #ifndef CAPACIDADE #define CAPACIDADE 10001 #endif struct Heap { int tamanho; int vetor[CAPACIDADE]; }; typedef struct Heap MaxHeap; /* Recebe um heap h e imprime o conteúdo do heap */ void imprimeHeap (MaxHeap* h) { int i; printf ("Heap h\n"); for (i = 1; i <= h->tamanho; i++) { printf ("heap[%d] : %d\n", i, h->vetor[i]); } printf ("\n"); } /* Recebe um heap h, os índices de dois filhos Esquerdo e Direito e devolve o inteiro que representa o de menor valor. */ int obtemFilhoMenor (MaxHeap* h, int filhoEsquerdo, int filhoDireito) { int minimo; int indiceMinimo; if (filhoEsquerdo <= (h->tamanho) && filhoDireito <= (h->tamanho)) { minimo = h->vetor[filhoEsquerdo]; indiceMinimo = filhoEsquerdo; if (minimo > h->vetor[filhoDireito]) { minimo = h->vetor[filhoDireito]; indiceMinimo = filhoDireito; } return indiceMinimo; } else if (filhoEsquerdo <= (h->tamanho) && filhoDireito > (h->tamanho)) { return filhoEsquerdo; } else if (filhoDireito <= (h->tamanho) && filhoEsquerdo > (h->tamanho)) { return filhoDireito; } else { /* Ambos são maiores que o heap: devolve valor que não aparecerá no heap-> */ return CAPACIDADE + 1; } } /* Recebe um heap h, os índices de dois filhos Esquerdo e Direito e devolve o inteiro que representa o de maior valor. */ int obtemFilhoMaior (MaxHeap* h, int filhoEsquerdo, int filhoDireito) { int maximo; int indiceMaximo; if (filhoEsquerdo <= (h->tamanho) && filhoDireito <= (h->tamanho)) { maximo = h->vetor[filhoEsquerdo]; indiceMaximo = filhoEsquerdo; if (maximo < h->vetor[filhoDireito]) { maximo = h->vetor[filhoDireito]; indiceMaximo = filhoDireito; } return indiceMaximo; } else if (filhoEsquerdo <= (h->tamanho) && filhoDireito > (h->tamanho)) { return filhoEsquerdo; } else if (filhoDireito <= (h->tamanho) && filhoEsquerdo > (h->tamanho)) { return filhoDireito; } else { /* Ambos são maiores que o heap: devolve valor que não aparecerá no heap-> */ return CAPACIDADE + 1; } } /* Recebe um Heap h e um índice i pertencente ao Heap. Devolve a nova posição do elemento que era inicialmente i. */ int rebaixa (int i, MaxHeap* h) { int filhoEsquerdo; int filhoDireito; int filhoMaior; int filhoMenor; int aux; while (i <= (h->tamanho)) { filhoEsquerdo = 2 * i; filhoDireito = 2 * i + 1; filhoMaior = obtemFilhoMaior(h, filhoEsquerdo, filhoDireito); filhoMenor = obtemFilhoMenor(h, filhoEsquerdo, filhoDireito); if ((filhoMaior <= h->tamanho) && (h->vetor[i] < h->vetor[filhoMaior])) { aux = h->vetor[filhoMaior]; h->vetor[filhoMaior] = h->vetor[i]; h->vetor[i] = aux; i = filhoMaior; } else if ((filhoMenor <= h->tamanho) && (h->vetor[i] < h->vetor[filhoMenor])) { aux = h->vetor[filhoMenor]; h->vetor[filhoMenor] = h->vetor[i]; h->vetor[i] = aux; i = filhoMenor; } else { return i; } } return i; } /* Recebe um heap h. Devolve o elemento que estava na raiz do heap. */ int extraiMaximo (MaxHeap* h) { int maximo; if ((h->tamanho) > 1) { maximo = h->vetor[1]; h->vetor[1] = h->vetor[(h->tamanho)]; (h->tamanho) = (h->tamanho) - 1; rebaixa (1, h); } else if (h->tamanho == 1) { maximo = h->vetor[1]; (h->tamanho) = 0; } else { maximo = -1; } return maximo; } /* Recebe um Heap e um inteiro i. Devolve o novo valor de i após tentar realizar promoções ao valor que estava na posição inicial de i. */ int promove (int i, MaxHeap* h) { int aux; while (i > 1) { if (h->vetor[i] > h->vetor[ i / 2 ]) { aux = h->vetor[i]; h->vetor[i] = h->vetor[i / 2]; h->vetor[i / 2] = aux; i = i / 2; } else { return i; } } return i; } /* Recebe um Heap h e um vertice x. Insere x em h e devolve o índice de x em h. */ int insere (int x, MaxHeap* h) { int indiceX = -1; h->tamanho = (h->tamanho) + 1; if (h->tamanho < CAPACIDADE) { h->vetor[h->tamanho] = x; indiceX = h->tamanho; indiceX = promove (indiceX, h); } return indiceX; } /* Recebe um MaxHeap e um número n. Gera n números pseudo aleatórios e insere cada um no MaxHeap. */ void incluiElementos(MaxHeap* maxHeap, int n) { int i; int pseudoAleatorio; for (i = 0; i < n; i++) { pseudoAleatorio = rand() % n; insere (pseudoAleatorio, maxHeap); } } /* Recebe um vetor e seu tamanho n. Devolve 0 se não estiver em ordem não descrescente e devolve 1 se estiver. */ int estaOrdenado(int vetor[CAPACIDADE], int n) { int i; for (i = 0; i < n - 1; i++) { if (vetor[i] > vetor[i + 1]) { return 0; } } return 1; } /* Recebe um vetor e seu tamanho n. Imprime os elementos de 0 a n em v. */ void imprimeVetor (int vetor[CAPACIDADE], int n) { int i; for (i = 0; i < n; i++) { if (i % 10 == 0) { printf ("\n"); } printf ("%5d ", vetor[i]); } printf ("\n"); } /* Recebe um MaxHeap, um vetor e um número n tal que 1 <= n <= 10000. Ordena os elementos do vetor de maneira não decrescente. */ void HeapSort (MaxHeap* maxHeap, int vetor[CAPACIDADE], int n) { int i; for (i = n - 1; i >= 0; i--) { vetor[i] = extraiMaximo(maxHeap); } } int main() { int n = 0; MaxHeap maxHeap; int vetor[CAPACIDADE] = {0, }; maxHeap.tamanho = 0; srand(time(NULL)); printf ("*** Ordenação com HeapSort ***\n\n"); while (n <= 0) { printf ("Digite o tamanho do vetor a ser ordenado (0 < n <= 10000): "); scanf ("%d", &n); } if (n <= 10000) { incluiElementos(&maxHeap, n); HeapSort (&maxHeap, vetor, n); printf ("Vetor Ordenado: "); if (estaOrdenado (vetor, n) == 1) { printf ("Sim.\n"); } else { printf("Não.\n"); } imprimeVetor (vetor, n); } else { printf ("Forneça n no intervalo [1 - 10000].\n"); } return 0; }
Utilização de Ponteiros em C (2)
Eliminando elementos repetidos de uma sequência
Nenhum comentário foi encontrado.
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Não consigo acessar os modos de desempenho (2)
Ubuntu — tentando iniciar o windows? (0)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba