# bon

C++博客 :: 首页 :: 联系 :: 聚合  :: 管理

•

### 评论排行榜

2009年4月30日 #

Recently, I began to peruse the CLRS (Introduction to Algorithms).

Now I would like to scan all basic algorithms, especially sorting and searching.

Let me first present a classic sorting algorithm - merge sort. Here is my code. Before I reach here, some mistakes are made, thus I note these "pitfalls" in the code

#include <stdlib.h>
#include <stdio.h>
#define MAX 1e9    // the biggest possible value of a int number is 2^31 - 1 which is approximately 10^9
#define SIZE 10

int *a;
int *b;
int *c;

// merge [p, q] and [q+1, r], where within each range number are sorted
void merge(int p, int q, int r)
{
int k;
int length = r - p +1;            // the length the range to be merge
for (k = 0; k < q - p + 1; k++) {
b[k] = a[p + k];             // copy number in a[p, q] to b
}
b[k] = MAX;             // b[k] = MAX, not b[k+1]=MAX
for (k = 0; k < r - q; k++) {
c[k] = a[q + 1 + k];             // copy number in a[q+1, r] to c
}
c[k] = MAX;             // c[k] = MAX, not c[k+1]=MAX

/* BEGIN merging */
int i = 0;
int j = 0;
for (k=0;k<length;k++) {             // do exactly length times of copy
if (b[i] < c[j]) {
a[p + k] = b[i++];          // be careful! a[p, r] is a whole range now, and watch out the base "p"
} else {
a[p + k] = c[j++];
}
}
}

void merge_sort(int l, int u)
{
if (l == u) return;             // when to stop recursion? only one number needs no sorting
int m = (l + u)/2;
merge_sort(l, m);
merge_sort(m + 1, u);
merge(l, m, u);
}

int main()
{
a = (int*)malloc(SIZE * sizeof(int));
b = (int*)malloc(SIZE * sizeof(int));          // cache, avoid many "malloc" in the merge function
c = (int*)malloc(SIZE * sizeof(int));          // this trick is from "Programming Pearls"
int i;
for (i = 0; i < SIZE; i++) {
a[i] = SIZE - i;
}
merge_sort(0, SIZE - 1);                    // watch out the range
for (i = 0; i < SIZE; i++) {
printf("%d\n", a[i]);
}
return 1;
}

posted @ 2009-04-30 13:57 bon 阅读(142) | 评论 (0)编辑 收藏

2008年7月31日 #

摘要: 未完  阅读全文
posted @ 2008-07-31 10:51 bon 阅读(184) | 评论 (0)编辑 收藏

2008年7月28日 #

摘要: 水题  阅读全文
posted @ 2008-07-28 16:48 bon 阅读(289) | 评论 (0)编辑 收藏

2008年7月25日 #

摘要: 详细介绍KMP算法以及POJ上的一道题目  阅读全文
posted @ 2008-07-25 11:45 bon 阅读(247) | 评论 (0)编辑 收藏

2008年7月9日 #

摘要: kddcup08 (1)  阅读全文
posted @ 2008-07-09 09:55 bon 阅读(469) | 评论 (0)编辑 收藏

2008年6月29日 #

posted @ 2008-06-29 10:52 bon 阅读(995) | 评论 (1)编辑 收藏

2008年6月9日 #

摘要: 解题报告 rather tricky  阅读全文
posted @ 2008-06-09 15:29 bon 阅读(378) | 评论 (0)编辑 收藏

2008年5月27日 #

摘要: pku 1936 解题报告+LCS的理解  阅读全文
posted @ 2008-05-27 15:46 bon 阅读(560) | 评论 (0)编辑 收藏

2008年5月24日 #

摘要: 递归 树的深度 左儿子右兄弟  阅读全文
posted @ 2008-05-24 20:34 bon 阅读(387) | 评论 (0)编辑 收藏

摘要: hash表  阅读全文
posted @ 2008-05-24 11:34 bon 阅读(838) | 评论 (1)编辑 收藏