http://snippets.dzone.com/posts Sat, 26 Jul 2008 20:11:10 GMT DZone Snippets: merge-sort code http://snippets.dzone.com/posts/show/4585 Implements the classic Merge-sort algorithm. <br /> <br />Time: theta(lg(n)) <br />Space: theta(n) <br /> <br /><code> <br />#include <stdio.h> <br />#include <stdlib.h> <br />#include <string.h> <br /> <br />void printv(char* in, int *v, int n) { <br /> printf("%s", in); <br /> int i = 0; <br /> for (; i < n; ++i) <br /> printf("%d ", v[i]); <br /> printf("\n"); <br />} <br /> <br />void merge(int *v, int p, int q, int r) { <br /> int i = p; <br /> int j = q + 1; <br /> <br /> int *tmp = (int*)malloc((r - p + 1) * sizeof(int)); <br /> int k = 0; <br /> <br /> while ((i <= q) && (j <= r)) { <br /> if (v[i] < v[j]) <br /> tmp[k++] = v[i++]; <br /> else <br /> tmp[k++] = v[j++]; <br /> } <br /> <br /> while (i <= q) <br /> tmp[k++] = v[i++]; <br /> <br /> while (j <= r) <br /> tmp[k++] = v[j++]; <br /> <br /> memcpy(v + p, tmp, (r - p + 1) * sizeof(int)); <br /> free(tmp); <br />} <br /> <br />void mergeS(int *v, int p, int r) { <br /> if (p < r) { <br /> int q = (p + r) / 2; <br /> mergeS(v, p, q); <br /> mergeS(v, q + 1, r); <br /> merge(v, p, q, r); <br /> } <br />} <br /> <br />int main(int argc, char *argv[]) { <br /> int n = 10; <br /> int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1}; <br /> <br /> printv("V: ", v, n); <br /> mergeS(v, 0, n - 1); <br /> printv("V: ", v, n); <br /> <br /> return 0; <br />} <br /></code> Fri, 28 Sep 2007 06:40:13 GMT http://snippets.dzone.com/posts/show/4585 scvalex (Alexandru Scvortov)