merge sort

[ack_attack]

kakak, aku mau share nih, tentang algoritma "merge sort", semoga berguna ya kakak....

langsung aja dech....

"merge sort" adalah jenis algoritma pengurutan "sorting" yang bersistem "divide and conquer" atau "pecah belah dan taklukkan", langsung saja ke algoritmanya ya kak....

Semisal kita mempunyai array :

A = [ 99, 5, 0, 2, 6, 1, 7, 8 ];

Nah, cara menyelesaikan masalah ini dengan cara "merge sort" adalah sebagai berikut :

1. pecah belah array tersebut menjadi beberapa bagian dan per bagian berisikan 2 data dan pastikan tiap data per bagian tersebut sudah diurutkan (dengan fungsi "merge()") :

Figure 1.0 : Pseudocode fungsi "merge()" (Taken from wikipedia)

Code:

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

Note : Pada tahapan ini "panjang_array_kiri" = 1; "panjang_array_kanan" = 1

Code:

[ 99, 5 ]     [ 0, 2 ]     [ 6, 1 ]     [ 7, 8 ] ---> belum diurutkan
[ 5, 99 ]     [ 0, 2 ]     [ 1, 6 ]     [ 7, 8 ] ---> sudah diurutkan dengan fungsi "merge()"

2. "panjang_array_kiri" dan "panjang_array_kanan" kalikan dengan 2

Note : Pada tahapan ini "panjang_array_kiri" = 2; "panjang_array_kanan" = 2

Code:

[ 5, 99, 0, 2 ]    [ 1, 6, 7, 8 ] ---> belum diurutkan
[ 0, 2, 5, 99 ]    [ 1, 6, 7, 8 ] ---> sudah diurutkan dengan fungsi "merge()"

3. "panjang_array_kiri" dan "panjang_array_kanan" kalikan dengan 2

Note : Pada tahapan ini "panjang_array_kiri" = 4; "panjang_array_kanan" = 4

Code:

[ 0, 2, 5, 99, 1, 6, 7, 8 ] ---> belum diurutkan
[ 0, 1, 2, 5, 6, 7, 8, 99 ] ---> ini adalah array final kita, sudah diurutkan dengan fungsi "merge()"

Ini adalah contoh program aku :

Code:

/*
* div_test - Hybrid Merge Sort Algorithm
*
* Programmer : ack_attack
*/
#include <stdio.h>

static void print_integer_array(int *array, int array_length) {
    int i;

    for (i = 0; i < array_length; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

static void hybrid_subsort(int *array, int array_length) {
        int i0, i1, var, temp;

        i0 = 0;
        i1 = 1;
        var = 0;
        while (i0 < array_length) {
                for (i1 = 0; i1 <= i0; i1++) {
                        if (array[var] <= array[i1]) {
                                temp = array[i1];
                                array[i1] = array[var];
                                array[var] = temp;
                        }
                }
                i0++;
                var++;
        }

        return;
}

static void merge(int array0[], int length0, int array1[], int length1, int buffer[]) {
    int state_point0, state_point1, nbytes;

    state_point0 = 0;
    state_point1 = 0;
    nbytes = 0;
    while ((state_point0 < length0) || (state_point1 < length1)) {
        if (state_point0 >= length0) {
            buffer[nbytes] = array1[state_point1];
            state_point1++;
            nbytes++;
        }
        else if (state_point1 >= length1) {
            buffer[nbytes] = array0[state_point0];
            state_point0++;
            nbytes++;
        }
        else if (array0[state_point0] <= array1[state_point1]) {
            buffer[nbytes] = array0[state_point0];
            state_point0++;
            nbytes++;
        }
        else {
            buffer[nbytes] = array1[state_point1];
            state_point1++;
            nbytes++;
        }
    }
}

static void hybrid_merge_sort(int core_array[], int core_scratch[], int array_length) {
    int ia0, ia1;
    int subarray_length0, subarray_length1;
    int temp_length, i;
    int half;

    subarray_length0 = 1;
    subarray_length1 = 1;
    while (subarray_length0 < array_length) {
        ia0 = 0;
        while (ia0 < array_length) {
            ia1 = ia0 + subarray_length0;

            if (ia1 > array_length) {
                for (i = ia0; i < array_length; i++) {
                    core_scratch[i] = core_array[i];
                }
            }
            else {
                if (ia1 + subarray_length0 >= array_length) {
                    subarray_length1 = array_length - ia1;
                }
                hybrid_subsort(&core_array[ia0], subarray_length0);
                        hybrid_subsort(&core_array[ia1], subarray_length1);
                merge(&core_array[ia0], subarray_length0, &core_array[ia1], subarray_length1, &core_scratch[ia0]);
            }

            ia0 += subarray_length0 * 2;
        }
        subarray_length0 *= 2;
        subarray_length1 = subarray_length0;
        for (i = 0; i < array_length; i++) {
            core_array[i] = core_scratch[i];
        }
    }
}

int main(void) {
    /* requirements for "merge" function */
    int array0[] = { 1, 2, 3 };
    int array1[] = { 1, 1000, 2000, 4000 };
    int scratch0[] = { 0, 0, 0, 0, 0, 0, 0 };
    int scratch1[] = { 0, 0, 0, 0, 0, 0, 0 };

    /* requirements for "merge_sort" function */
    int core_array2[] = { 45, 46, 1, 99, 2, 9000, 10000, 1000 };
    int core_scratch2[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    int core_array3[] = { 900, 5000, 45, 2000, 3456, 67, 6800, 45, 567, 23, 5, 9, 3, 46, 99, 1500, 56, 0, 5, 3, 78, 23, 14, 67, 999, 9999 };
    int core_scratch3[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

    /* for general "loop" function */
    int i;

    printf("-------- Base array for \"merge\" function  --------\n");
    printf("First : ");
    for (i = 0; i < 3; i++) {
        printf("%d ", array0[i]);
    }
    printf("\n");
    printf("Second : ");
    for (i = 0; i < 4; i++) {
        printf("%d ", array1[i]);
    }
    printf("\n\n");

    merge(array0, 3, array1, 4, scratch0);
    printf("-------- 1, 2 merge --------\n");
    for (i = 0; i < 7; i++) {
        printf("%d ", scratch0[i]);
    }
    printf("\n\n");

    merge(array1, 4, array0, 3, scratch1);
    printf("-------- 2, 1 merge --------\n");
    for (i = 0; i < 7; i++) {
        printf("%d ", scratch1[i]);
    }
    printf("\n\n");

    printf("-------- Base array for \"merge_sort\" function --------\n");
    printf("Array 1 : ");
    print_integer_array(core_array2, 8);
    printf("\n");

    printf("Array 2 : ");
    print_integer_array(core_array3, 26);
    printf("\n");

    hybrid_merge_sort(core_array2, core_scratch2, 8);
    hybrid_merge_sort(core_array3, core_scratch3, 26);

    printf("-------- \"merge_sort\" runtest III --------\n");
    print_integer_array(core_array2, 8);
    printf("\n");

    printf("-------- \"merge_sort\" runtest IV --------\n");
    print_integer_array(core_array3, 26);
    printf("\n");

    return 0;
}

Maaf kak kalau threadnya tidak sempurna, soalnya (maaf : saya mau ke belakang.. ^_^)
Selamat belajar buat semua....

[Super Moderator]

buset,gue

[ToNhoW]

(03-23-2012 06:38 PM)linuxer46 Wrote:  buset,gue

wkwkkwkw

[ditatompel]

Wah ajib om logicnya..
Ane selalu pusing klo ada yg macem ginian..
Ane pelajari dulu omz..

[RieqyNS13]

yah,,di C
ada tutornya untuk yg di C++ ga' om ?