Monday, April 15, 2013

Algoritma pengurutan data dengan 5 metode sorting

1. Bubble Sort
kita dapat mengcoding sorting bubble sort sebagai berikut :


#include
int tukar=0;

void main()
{
    int data[]= {/*di isi banyaknya data*/};
    int n=50;
    int i;

    printf("======================================\n");
    printf(" Perbandingan Banyak Pertukaran Data Algoritma sorting\n");
    printf("======================================\n\n");

    printf("hasil pengurutan berdasarkan bubble sort :\n");

    printf("\n\ndata sebelum Di sorting : \n"); tampilkan_larik(data,n);printf("\n\n");
    bubble_sort(data,n);
    printf("\n\ndata sesudah Di sorting : \n"); tampilkan_larik(data,n);
    printf("\nberdasarkan sorting bubble sort terjadi %d pertukaran\n\n",tukar);
}

void bubble_sort (int data[], int n)
{
    int tahap, j, tmp;
    for(tahap = 1; tahap < n; tahap++)
    {
        for(j=0; j < n-tahap; j++)

        if(data[j] > data[j+1])
        {
            tmp = data[j];
            data[j] = data[j+1];
            data[j+1] = tmp;
            tukar=tukar+1;
            printf ("\nHasil pertukaran ke = %d\n", tukar); tampilkan_larik (data,n);
        }
    }
}

void tampilkan_larik(int data[],int n)
{
    int i;
    for(i=0 ; i    printf("%d ",data[i]);
    printf ("\n");
}


Setelah itu kita dapat mengkompilenya (tentunya setelah kita memasukkan data yg akan di compile) semisal kita mempunyai 50 data yang akan di urutkan, dengan data sebagai berikut : 12 15 4 25 45 10 19 9 32 33 44 23 54 12 7 8 35 46 9 12 32 4 56 76 9 34 11 13 32 45 33 11 7 89 65 45 36 78 54 23 56 32 12 56 78 89 7 9 56 34
maka hasil kompilasi yang kita dapatkan adalah :


dari hasil kompilasi dapat di ketahui bahwa untuk mengurutkan data yang ada dibutuhkan 448 kali pertukaran data dengan execution time 6,290 detik

2. Insertion Sort
#include
int tukar=0;

void main()
{
    int data[]= {/*di isi banyaknya data*/}
    int n=50;
    int i;

    printf("======================================\n");
    printf(" Perbandingan Banyak Pertukaran Data Algoritma sorting\n");
    printf("======================================\n\n");


    printf("hasil pengurutan berdasarkan Insertion sort :\n");

    printf("\n\ndata sebelum Di sorting : \n"); tampilkan_larik(data,n);printf("\n\n");
    insertion_sort(data,n);
    printf("\n\ndata sesudah Di sorting : \n"); tampilkan_larik(data,n);
    printf("\nberdasarkan sorting insertion sort terjadi %d pertukaran\n\n",tukar);
}

void insertion_sort(int data[], int n)
{
    int temp,key,i,a;
    for(a=0;a    {
        key=data[a];
        i=a-1;
        while(i>=0 && data[i]>key)
        {
            data[i+1]=data[i];
            i=i-1;
            data[i+1]=key;
            tukar=tukar+1;
            printf ("Hasil pertukaran ke %d:", tukar); tampilkan_larik (data,n);
        }
    }
}

void tampilkan_larik(int data[],int n)
{
    int i;
    for(i=0 ; i    printf("%d ",data[i]);
    printf ("\n");

}
dengan data yang sama maka hasil kompilasi yang kita dapatkan adalah :


dari hasil kompilasi dapat di ketahui bahwa untuk mengurutkan data yang ada dibutuhkan 448 kali pertukaran data dengan execution time 5,750 detik

3. Selection Sort
#include
int tukar=0;

void main()
{
    int data[]= {/*di isi banyaknya data*/}
    int n=50;
    int i;

    printf("======================================\n");
    printf(" Perbandingan Banyak Pertukaran Data Algoritma sorting\n");
    printf("======================================\n\n");


    printf("hasil pengurutan berdasarkan Selection sort :\n");

    printf("\n\ndata sebelum Di sorting : \n"); tampilkan_larik(data,n);printf("\n\n");
    selection_sort(data,n);
    printf("\n\ndata sesudah Di sorting : \n"); tampilkan_larik(data,n);
    printf("\nberdasarkan sorting selection sort terjadi %d pertukaran\n\n",tukar);
}

void selection_sort(int data[], int n)
{
    int tmp,a,b;
    for(a=0;a    {
        for(b=a+1;b        {
            if(data[a]>data[b])
            {
                tmp=data[b];
                data[b]=data[a];
                data[a]=tmp;
                tukar=tukar+1;printf("\n\npertukaran ke : %d\n",tukar); tampilkan_larik(data,50);
            }
        }
    }
}

void tampilkan_larik(int data[],int n)
{
    int i;
    for(i=0 ; i    printf("%d ",data[i]);
    printf ("\n");

}

dengan data yang sama maka hasil kompilasi yang kita dapatkan adalah :


dari hasil kompilasi dapat di ketahui bahwa untuk mengurutkan data yang ada dibutuhkan 352 kali pertukaran data dengan execution time 4,420 detik

4. Merge Sort
#include
#define MAX 50
int tukar=0;

int main()
{

    int i,n=50;

    int data[]= {/*di isi banyaknya data*/}

    printf("======================================\n");
    printf(" Perbandingan Banyak Pertukaran Data Algoritma sorting\n");
    printf("======================================\n\n");


    printf("hasil pengurutan berdasarkan merge sort :\n");

    printf("\n\ndata sebelum Di sorting : \n"); tampilkan_larik(data,n);printf("\n\n");
    partition(data,0,n-1);
    printf("\ndata sesudah Di sorting : \n"); tampilkan_larik(data,n);
    printf("\nberdasarkan sorting merge sort terjadi %d pertukaran\n\n",tukar);

   return 0;
}

void partition(int arr[],int low,int high)
{
    int mid,a;
    if(low    {
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high)
{
    int i,m,k,l,temp[MAX],a;

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high))
    {
         if(arr[l]<=arr[m])
         {
             temp[i]=arr[l];
             l++;
         }
         else
         {
             temp[i]=arr[m];
             m++;
         }
         i++;
         tukar=tukar+1;printf("\n\npertukaran ke : %d\n",tukar); tampilkan_larik(arr,50);
    }

    if(l>mid)
    {
        for(k=m;k<=high;k++)
        {
            temp[i]=arr[k];
            i++;
        }
        tukar=tukar+1;printf("\n\npertukaran ke : %d\n",tukar); tampilkan_larik(arr,50);
    }
    else
    {
         for(k=l;k<=mid;k++)
         {
             temp[i]=arr[k];
             i++;
         }
         tukar=tukar+1;printf("\n\npertukaran ke : %d\n",tukar); tampilkan_larik(arr,50);
    }

    for(k=low;k<=high;k++)
    {
        arr[k]=temp[k];
    }
    tukar=tukar+1;printf("\n\npertukaran ke : %d\n",tukar); tampilkan_larik(arr,50);
}

void tampilkan_larik(int data[],int n)
{
    int i;
    for(i=0 ; i    printf("%d ",data[i]);
    printf ("\n");

}

dengan data yang sama maka hasil kompilasi yang kita dapatkan adalah :


dari hasil kompilasi dapat di ketahui bahwa untuk mengurutkan data yang ada dibutuhkan 316 kali pertukaran data dengan execution time 3,550 detik

5. Quick Sort
#include
int tukar=0;

void main()
{
    int data[]= {/*di isi banyaknya data*/}
    int n=50;
    int i;

    printf("======================================\n");
    printf(" Perbandingan Banyak Pertukaran Data Algoritma sorting\n");
    printf("======================================\n\n");


    printf("hasil pengurutan berdasarkan Quick sort :\n");

    printf("\n\ndata sebelum Di sorting : \n"); tampilkan_larik(data,n);printf("\n\n");
    quick_Sort( data, 0, n-1);
    printf("\n\ndata sesudah Di sorting : \n"); tampilkan_larik(data,n);
    printf("\nberdasarkan sorting selection sort terjadi %d pertukaran\n\n",tukar);

}


void quick_Sort( int data[], int l, int r)
{
    int j;

    if( l < r )
    {
        // divide and conquer
        j = partition( data, l, r);
        quick_Sort( data, l, j-1);
        quick_Sort( data, j+1, r);
    }
}

int partition( int data[], int l, int r)
{
    int pivot, i, j, t;
    pivot = data[l];
    i = l; j = r+1;

    while( 1)
    {
        do ++i; while( data[i] <= pivot && i <= r );
        do --j; while( data[j] > pivot );
        if( i >= j ) break;
        t = data[i]; data[i] = data[j]; data[j] = t;
        tukar=tukar+1;printf("pertukaran ke : %d\n",tukar); tampilkan_larik(data,50);

    }
    t = data[l]; data[l] = data[j]; data[j] = t;
    tukar=tukar+1;printf("pertukaran ke : %d\n",tukar); tampilkan_larik(data,50);


    return j;
}

void tampilkan_larik(int data[],int n)
{
    int i;
    for(i=0 ; i    printf("%d ",data[i]);
    printf ("\n");

}

dengan data yang sama maka hasil kompilasi yang kita dapatkan adalah :


dari hasil kompilasi dapat di ketahui bahwa untuk mengurutkan data yang ada dibutuhkan 70 kali pertukaran data dengan execution time 1,470 detik

Setelah kita membahas satu per satu metode sorting di atas dapat kita simpulkan bahwa sorting dengan pertukaran data ter singkat adalah Quick Sort disusul oleh Merge, Selection, Insertion dan Bubble.

No comments:

Post a Comment

Kebahagiaan sejati bukanlah pada saat kita berhasil meraih apa yg kita perjuangkan, melainkan bagaimana kesuksesan kita itu memberi arti atau membahagiakan orang lain.