Merge Sort

Algoritma Merge Sort

Algoritma Merge adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data mu. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

    Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

    Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

    Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data

    berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Misalkan kita mau mengurutkan beberapa angka yaitu 38,27,43,3,9,82 dan 10. Maka untuk mengurutkan menggunakan merge-sort langkah-langkahnya seperti gambar dibawah ini 

Algoritma untuk prosedur MergeSortnya :

mergesort(low, high) { int mid; if(low<high) { mid=(low+high)/2; mergesort(low,mid); mergesort(mid+1,high); merge(low,high,mid); } ) Merge( low, mid, high) { int h,i,j,k,b[50]; h=low; i=low; j=mid+1; while((h<=mid)&&(j<=high)) { if(A[h]<A[j]) { b[i]=A[h]; h++; }else{ b[i]=A[j]; j++; } i++; } if(h>mid) { for(k=j;k<=high;k++) { b[i]=A[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=A[k]; i++; } } for(k=low;k<=high;k++) { A[k]=b[k]; } }

Coding with c++ :

#include <iostream>

using namespace std;

void MergeSort(int low, int high);

void Merge(int , int , int );

int A[50];

int main()

{

 int i, elemen;

 cout<<"Berapa banyak elemen yang ingin disusun ? "; cin>>elemen;

 cout<<endl;

 cout<<"Masukkan " <<elemen<<" elemen: \n";cout<<endl;

 for(i=1;i<=elemen;i++)

 {

   cout << "Elemen ke-"<<i<<" = ";

   cin>>A[i];

 }

 cout<<endl;

 MergeSort(1,elemen);

 cout<<endl;

 cout<<"Setelah di mergesort: \n\n";

 for(i=1;i<=elemen;i++)

 {

    cout<< A[i] <<" ";

 }

 cout<< endl << endl;

 return 0;

}

//prosedure Mergesort

void MergeSort(int low, int high)

{

 int mid;

 if(low<high)

 {

    mid = (low+high)/2;

    MergeSort(low,mid);

    MergeSort(mid+1, high);

    Merge(low, mid, high);

 }

}

//Prosedure Merge

void Merge(int low, int mid, int high)

{

 int h,i,j,k,b[50];

 h=low;

 i=low;

 j=mid+1;

 while((h<=mid)&&(j<=high))

 {

    if(A[h]<A[j])

    {

       b[i]=A[h];

       h++;

    }else{

       b[i]=A[j];

       j++;

    }

   i++;

 }

 if(h>mid)

 {

    for(k=j;k<=high;k++)

    {

      b[i]=A[k];

      i++;

    }

 }else{

    for(k=h;k<=mid;k++)

    {

      b[i]=A[k];

      i++;

    }

 }

 for(k=low;k<=high;k++)

 {

    A[k]=b[k];

 }

}

Output:

Indonesia Menangis

31 September 2010

Seorang bocah menangis memanggil ibunya

”Ibu…ibu… aku takut… “Kenapa orang orang semua lari ke atas bu..’’?kenapa bu”?

“Huuhuuuuhuuuu…”huhuhuhuhuhuhuu….”Ibu…jawab buuu….”!

Sang ibu yang ditanya pun tak sanggup menjawab pertanyaan anaknya karena panik melarikan diri ke tempat yang lebih aman…

Sementara di pojokan sebelah sana …

“Ayah ayah…ibu mana…” ? “Ibu mana…”?

”Kenapa orang orang panic seperti itu ayah…”?

“Apa yang terjadi sekarang…”?

“Ayah… ayah emang kita lagi di mana”?

“Ayah rumah kita kok tidak kelihatan lagi…”?

“Kenapa banyak air di bawah yahh”?

“Air apa itu”?

“Kenapa rumah rumah pada terbawa hanyut seperti itu”?”Ayahhhh……”

Sang ayah yang ditanyai anaknya hanya bisa menjawab dengan tangisan…

Perih,,,,penuh rintih

Atas apa yang terjadi di negeri pertiwi ini…

Sawah ladang,harta benda, rumah tempat berteduh,kasur empuk untuk tempat tidur nyenyak semua sudah terbawa oleh air bah yang melanda..tidak ada lagi yang tersisa ,yang tersisa hanyalah puing puing bangunan yang lapuk terkena air bah..

Deraian air mata berjatuhan di bumi ini…

Indonesia menangis…

Tak kuasa lagi alam memberi peringatan halus kepada manusia yang ada di muka bumi ..sehingga ia memberi peringatan atas kehendak Allah kepada manusia dengan cara yang memillukan….

Indonesia menangis…

Rumah yang hancur terbawa arus,sawah yang terkena lava panas,tsunami dan air bah yang melanda.. inikah yang kita mau??

Lantas kalau sudah seperti ini siapa yang patut disalahkan?

Apakah karena SBY yang tidak becus mengelola alam ini ???

Apakah SBY yang lalai pada proker proker kenegaraan yang sudah ia rancang ???

Astaghfirullahalazhimm…

Kenapa masih menyalahkan orang lain yang hanya di statuskan sebagai kepala negara??

Bukan kepala Negara tapi kita semua yang lalai terhadap seruan Allah,,yang mungkin terkadang sombong di muka bumi ini tidak patuh pada perintahnya…

Bukan kepala negara tapi kita semua yang seharusnya menjadi khalifah di muka bumi ini namun menjadi penghancur dan pengrusak bagi alam…

Kita semua…

Posted 12th October 2011 by Dewy Sartieka

Pentingnya Sebuah Hal Kecil

Pentingnya sebuah hal kecil

Bismillah

Sebuah kemunduran di era maju,,,

Karena hal kecil banyak yang terzalimi

Karena hal kecil banyak yang kecewa

Karena hal kecil banyak yang rusak

Karena hal kecil semuanya mengalami kemunduran

Pernahkan kita perhatikan atau mengevaluasi setiap kejadian?

Mengevaluasi setiap janji yang pernah terucap?

Mungkin benar tak ingat pada semuanya,untuk itulah Allah menganugrahkan saudara seiman agar bisa saling mengingatkan satu sama lain.

Sebuah hal sederhana jikalau diacuhkan saja dan tidak diperhatikan bisa menjadi hal yang membuat kita luka berdarah.

Ibarat sebuah batu besar,dilihat dari jarak jauhpun batu itu pasti sudah kelihatan oleh mata,dan di dalam hati tentunya ada rasa waspada yang kuat pada batu itu agar tak terjatuh ketika melewati jalan tersebut.Tapi ternyata di jalan itu masih terdapat batu batu kecil yang dari jauh tak tampak namun sebenarnya ada.Dari jauh tak melihat apa apa, yang ada hanya jalan mulus berkerikil kecil sedikit namun tak bahaya,tapi siapa tahu ternyata ketika melengah sedikit saja, kita bisa terpeleset menginjaknya sehingga membuat jatuh bahkan berdarah dan terluka parah.

Sebuah kisah sederhana lagi,ketika seorang anak yang berumur 5 tahun bermain bersama adiknya yang berusia 1 tahun di pekarangan rumah.Sementara orang tua maupun kakaknya sedang melakukan kesibukan masing masing di dalam rumah.

Bocah 5 tahun ini mendatangi ayahnya dan bertanya

“Ayah lubang yang ada di pekarangan rumah kita apa namanya”?

Ayahnya menjawab : “Tanya pada ibumu ayah sedang sibuk membaca koran”.

“Ibu,lubang yang ada di pekarangan rumah namanya apa?Ibu sedang memasak nak tanya kakakmu saja”!

“Kakak lubang yang ada di pekarangn rumah namanya apa”?

“Namanya sumur”!

“Cepatlah kk”,adik kita masuk ke dalam sumur !

Setelah mendengar hal itu semuanya langsung mengambil langkah seribu untuk melakukan pertolongan.

Seperti itulah kita,hal kecil yang sebenarnya bisa diatasi dari awal malah menjadi masalah besar yang tertumpuk karena tak ada respon sedikitpun.

Padahal kalau ada keinginan untuk langsung menghadapi dan melihat bahwa hal kecil itu juga merupakan unsur terpenting dalam kehidupan ini, musibah besar tak akan berlarut larut.

Sebenarnya kita sudah tahu bahwa itu tidak baik namun ntah mungkin masih banyak godaan,tak mampu untuk melaksanakan kebaikan itu.Tak mampu untuk melakukan perubahan lebih baik.Yang ada hanya masih tertanam di dalam hati bahwa itu tidak baik.Tertanam …tertanam …tertanam dan akhirnya menjadi sebuah kebiasaan yang sulit untuk dirubah.

Beginikah yang namanya Agent of Change?

Bukankah sebelum menjadi Agent of Change untuk negara ini kita dituntut untuk menjadi Agent of Change bagi diri kita sendiri?

Bukankah sebelum menjadi Agent of Change bagi keluarga,masyarakat dan bangsa,dituntut untuk menjadi Agent of Change bagi diri sendiri?

Bagaimana mungkin semuanya bisa terjadi jikalau kita melupakan hal kecil.Sebelum besar harus dari kecil dulu.Semuanya berproses.Namun setelah besar jangan lupakan yang kecil karena dari yang kecil itulah kita menjadi besar.

Posted 12th October 2011 by Dewy Sartieka