Skip to content

Instantly share code, notes, and snippets.

@Phitherek
Created March 9, 2012 10:52
Show Gist options
  • Save Phitherek/2006061 to your computer and use it in GitHub Desktop.
Save Phitherek/2006061 to your computer and use it in GitHub Desktop.
MergeSort w C wg algorytmu Hawka
#include <stdlib.h>
#include <stdio.h>
void merge(int* A, int p, int q, int r) {
printf("merge(A, %d, %d, %d)\n", p, q, r);
int a,b,i,j,k;
int* L;
int* P;
a = q-p+1;
printf("a=%d\n", a);
b = r-q;
printf("b=%d\n", b);
L = (int*) malloc(a*sizeof(int));
P = (int*) malloc(b*sizeof(int));
for(i=0;i<a;i++) {
L[i] = A[p+i];
printf("L[%d] = %d\n", i, L[i]);
}
for(j=0;j<b;j++) {
P[j] = A[q+1+j];
printf("P[%d] = %d\n", j, P[j]);
}
L[a] = 999999;
printf("L[%d] = %d\n", a, L[a]);
P[b] = 999999;
printf("P[%d] = %d\n", b, P[b]);
i=0;
printf("i=%d\n", i);
j=0;
printf("j=%d\n", j);
for(k=p; k<=r; k++) {
if(L[i] <= P[j]) {
A[k] = L[i];
printf("A[%d] = %d\n", k, A[k]);
i++;
printf("i=%d\n", i);
} else {
A[k] = P[j];
printf("A[%d] = %d\n", k, A[k]);
j++;
printf("j=%d\n", j);
}
}
}
void mergesort(int* A, int p, int r) {
printf("mergesort(A, %d, %d)\n", p, r);
int q;
if(p < r) {
q = (p+r)/2;
printf("q=%d\n", q);
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
int main(void) {
int tab[10];
int i;
srand(time(NULL));
printf("Wygenerowana tablica:\n");
for(i=0; i<10; i++) {
tab[i] = rand()%101;
printf("tab[%d] = %d\n", i, tab[i]);
}
printf("Uruchamiam mergesorta...\n");
mergesort(tab, 0, 10);
printf("Posortowana tablica:\n");
for(i=0; i<10; i++) {
printf("tab[%d] = %d\n", i, tab[i]);
}
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment