C++博客-bon

merge sort pitfalls

bon — Thu, 30 Apr 2009 05:57:00 GMT

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
#include
#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        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;
}

bon 2009-04-30 13:57 发表评论

KMP (2)

bon — Thu, 31 Jul 2008 02:51:00 GMT

摘要: 未完阅读全文

bon 2008-07-31 10:51 发表评论

POJ 2406

bon — Mon, 28 Jul 2008 08:48:00 GMT

摘要: 水题阅读全文

bon 2008-07-28 16:48 发表评论

KMP算法

bon — Fri, 25 Jul 2008 03:45:00 GMT

摘要: 详细介绍KMP算法以及POJ上的一道题目阅读全文

bon 2008-07-25 11:45 发表评论

KDDcup(1) 非完整版

bon — Wed, 09 Jul 2008 01:55:00 GMT

摘要: kddcup08 (1) 阅读全文

bon 2008-07-09 09:55 发表评论

KDDCUP08

bon — Sun, 29 Jun 2008 02:52:00 GMT

最近在Wei的指导下，跟显露参加了KDDCUP08的数据挖掘比赛。在这次比赛中的数据处理、算法以及其它的收获，会以连载的方式发出来，敬请各位关注。

bon 2008-06-29 10:52 发表评论

poj 2748

bon — Mon, 09 Jun 2008 07:29:00 GMT

摘要: 解题报告 rather tricky 阅读全文

bon 2008-06-09 15:29 发表评论

最长公共子序列（pku 1936）

bon — Tue, 27 May 2008 07:46:00 GMT

摘要: pku 1936 解题报告+LCS的理解阅读全文

bon 2008-05-27 15:46 发表评论

poj 3437

bon — Sat, 24 May 2008 12:34:00 GMT

摘要: 递归树的深度左儿子右兄弟阅读全文

bon 2008-05-24 20:34 发表评论

pku 3349

bon — Sat, 24 May 2008 03:34:00 GMT

摘要: hash表阅读全文

bon 2008-05-24 11:34 发表评论