Last active
September 23, 2023 14:53
-
-
Save olegon/27c2a880c9b932862e60ab5eb89be5b6 to your computer and use it in GitHub Desktop.
Algoritmo Mergesort feito na linguagem C.
This file contains 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
#include <stdio.h> | |
#include <stdlib.h> | |
void mergesort(int *v, int n); | |
void sort(int *v, int *c, int i, int f); | |
void merge(int *v, int *c, int i, int m, int f); | |
int main (void) { | |
int i; | |
int v[8] = { -1, 7, -3, 11, 4, -2, 4, 8 }; | |
mergesort(v, 8); | |
for (i = 0; i < 8; i++) printf("%d ", v[i]); | |
putchar('\n'); | |
return 0; | |
} | |
/* | |
Dado um vetor de inteiros v e um inteiro n >= 0, ordena o vetor v[0..n-1] em ordem crescente. | |
*/ | |
void mergesort(int *v, int n) { | |
int *c = malloc(sizeof(int) * n); | |
sort(v, c, 0, n - 1); | |
free(c); | |
} | |
/* | |
Dado um vetor de inteiros v e dois inteiros i e f, ordena o vetor v[i..f] em ordem crescente. | |
O vetor c é utilizado internamente durante a ordenação. | |
*/ | |
void sort(int *v, int *c, int i, int f) { | |
if (i >= f) return; | |
int m = (i + f) / 2; | |
sort(v, c, i, m); | |
sort(v, c, m + 1, f); | |
/* Se v[m] <= v[m + 1], então v[i..f] já está ordenado. */ | |
if (v[m] <= v[m + 1]) return; | |
merge(v, c, i, m, f); | |
} | |
/* | |
Dado um vetor v e três inteiros i, m e f, sendo v[i..m] e v[m+1..f] vetores ordenados, | |
coloca os elementos destes vetores, em ordem crescente, no vetor em v[i..f]. | |
*/ | |
void merge(int *v, int *c, int i, int m, int f) { | |
int z, | |
iv = i, ic = m + 1; | |
for (z = i; z <= f; z++) c[z] = v[z]; | |
z = i; | |
while (iv <= m && ic <= f) { | |
/* Invariante: v[i..z] possui os valores de v[iv..m] e v[ic..f] em ordem crescente. */ | |
if (c[iv] <= c[ic]) v[z++] = c[iv++]; | |
else v[z++] = c[ic++]; | |
} | |
while (iv <= m) v[z++] = c[iv++]; | |
while (ic <= f) v[z++] = c[ic++]; | |
} |
Thank you, it was very helpful
thanks , it was very helpful
thanks , it was very helpful
Hmmmm é mesmo é
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
ty, saved my day