Created
December 3, 2020 15:06
-
-
Save b2evandro/b8624fa3bee75c4d9ba13cc83c6e11b2 to your computer and use it in GitHub Desktop.
Implementação simples de HeapSort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// font do código inicial https://github.com/nmantzanas/Heapsort.git | |
#include <stdio.h> | |
void Heap(int vetor[], int quantidade_posi_vetor, int i) | |
{ | |
// pai_aux = para pai e temp = variavel para troca | |
int pai_aux = i, temp; | |
// define os filhois, tanto da esquerda como da direita sendo que i e o pai verdadeiro do vetor | |
int esquerda = 2 * i + 1; | |
int direita = 2 * i + 2; | |
// verifica se o filho da equerda e maior que o pai | |
if (esquerda < quantidade_posi_vetor && vetor[esquerda] > vetor[pai_aux]) | |
{ | |
// filho vira o pai | |
pai_aux = esquerda; | |
} | |
// verifica se o filho da direita e maior que o pai | |
if (direita < quantidade_posi_vetor && vetor[direita] > vetor[pai_aux]) | |
{ | |
// filho vira o pai | |
pai_aux = direita; | |
} | |
// se o houver um filho maior que o pai verdadeiro, eles trocam de posicao | |
if (pai_aux != i) | |
{ | |
temp = vetor[i]; | |
vetor[i] = vetor[pai_aux]; | |
vetor[pai_aux] = temp; | |
// chama novamente para verificar se tem algum filho maior que o pai, passando a possicao do novo pai | |
Heap(vetor, quantidade_posi_vetor, pai_aux); | |
} | |
} | |
void HeapSort(int vetor[], int quantidade_posi_vetor) | |
{ | |
int i, temp; | |
// divide o vetor para comecar a organizar e verificar quais sao os maiores | |
for (i = quantidade_posi_vetor / 2 - 1; i >= 0; i--) | |
{ | |
Heap(vetor, quantidade_posi_vetor, i); | |
} | |
// ordena vetor para que fiquem em ordem crescente | |
for (i = quantidade_posi_vetor - 1; i >= 0; i--) | |
{ | |
temp = vetor[i]; | |
vetor[i] = vetor[0]; | |
vetor[0] = temp; | |
Heap(vetor, i, 0); | |
} | |
} | |
void printvetor(int vetor[], int quantidade_posi_vetor) | |
{ | |
printf("["); | |
for (int i = 0; i < quantidade_posi_vetor - 1; i++) | |
{ | |
printf("%d, ", vetor[i]); | |
} | |
printf("%d ]\n", vetor[quantidade_posi_vetor - 1]); | |
} | |
int main() | |
{ | |
int vetor[] = {5, 13, 2, 25, 7, 17, 20, 8, 4, 1}; | |
// qunatos "obetos" teria no vetor = tamanho em byte do vetor, dividido por uma unidade do vetor | |
int quantidade_posi_vetor = sizeof(vetor) / sizeof(vetor[0]); | |
printf("Vetor inicial\n"); | |
printvetor(vetor, quantidade_posi_vetor); | |
HeapSort(vetor, quantidade_posi_vetor); | |
printf("Vetor Final\n"); | |
printvetor(vetor, quantidade_posi_vetor); | |
getchar(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment