MERGE SORT DAN INSERTION SORT ALGORITMA PEMROGRAMAN

MERGE SHORT

Metode "Merge Sort" atau sering juga disebut metode penggabungan. Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

Dalam algoritma juga mengenal dua macam pengurutan, yaitu

1.    urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar

2.    urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.

Dimana prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut divide and conquer. Hal ini dikarenakan algoritma sorting melakukan pembagian struktur data sebelum kemudian dioperasikan satu per satu. Intinya, algoritma ini menggunakan du aide utama, yaitu sebagai beriut:

1.    Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.

2.    Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut.

Untuk mengurutkan beberapa elemen, Merge Sort mengggunakan teknik Divide and Conquer  yang tahapan-tahapannya:
Tahapan-tahapannya:
1. Tahap Divide

Array A dibagi menjadi 2 bagian array , yaitu A1 dan A2. Kalau pembagiannya masih terlalu besar maka masing-masing bagian tadi dibagi menjadi dua bagian lainnya menjadi lebih kecil.

2. Tahap Recursion

Masing-masing bagian diurutkan dengan cara rekursif.

3. Tahap Conquer

Setelah diurutkan, masing-masing bagian array  digabungkan dan diurutkan sehingga menjadi satu array (Array A) yang utuh dan telah disusun secara urut.

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];  }  }

Nah sekarang kita coba 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];  } }

Outputnya

INSERTION SORT

          Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.

          Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sortingdisebut sebagai “pass“), dengan indeks dimulai dari 0.

     Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

Berikut adalah simulasi Algoritma Insertion Sort

Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Simulasi Insertion Sort

Dari gambaran proses pengurutan/ sorting  data di atas dapat diketahui  bagaimana data-data tersebut berpindah  posisi  dari satu index ke index lain dalam satu array.  Untuk detail proses pengurutan diatas, dapat disimak melalui detail simulasi berikut.

Data awal : 5, 2, 4, 6, 1, 3

Jumlah Index = 6   dimulai dari 0 s/d 5

Anggaplah index adalah ‘I’,

Untuk setiap proses pengurutan data, perbandingan data dimulai dari index kedua (dalam hal ini i=1)

Proses I:

i=1, x=1; j=0

x<j à2<5? — true  =2, 5, 4, 6, 1, 3

Proses II

i=2, j=1, x=2

x<j à  4<5 — true = 2, 4, 5, 6, 1, 3     j=j-1,      Jika benar    x=x-1

x<j à4<2 — false = 2, 4, 5, 6, 1, 3

Proses III

I=3, j=2, x=3

x<j à6<5 — false =  2, 4, 5, 6, 1, 3     j=j-1    jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena secara otomatis data yang ada disebelah kiri semuanya sudah terurut dengan benar.

Proses IV

i=4, j=3, x=4

x<j à1<6 — true = 2, 4, 5, 1, 6, 3   j=j-1,     jika benar  maka  x=x-1

x<j à 1<5 — true = 2, 4, 1, 5,6, 3  j=j-1 ,   jika benar  maka   x=x-1

x<j  à1<4  — true = 2, 1, 4, 5,6, 3  j=j-1,    jika benar  maka   x=x-1

x<j  à 1<2 — true =   1, 2, 4, 5,6, 3

Proses V

i=5, j=4, x=5

x<j à3<6  — true = 1, 2, 4, 5,3, 6  j=j-1, jika benar maka x=x-1

x<j à3<5 — true = 1, 2, 4, 3, 5, 6   j=j-1, jika benar maka x=x-1

x<j à3<4 — true = 1, 2, 3, 4, 5, 6  j=j-1, jika benar maka x=x-1

x<jà3<2 — false = 1, 2, 3, 4, 5, 6  j=j-1

berikut adalah contoh codingannya:

 #include<iostream>

#include <conio.h>

int main()

{

int data[]={5, 2, 4, 6, 1, 3};

cout<<“sebelum disorting: “;

for(int i=0; i<6; i++)

cout<<data[i] <<“,  “;

cout<<endl <<endl;

for(int i=1; i<6; i++)

{

int j=i;

while(data[j]<data[j-1])

{

int tmp=data[j];

data[j]=data[j-1];

data[j-1]=tmp;

j­­--;

}

}

cout<<“Setelah disorting: “;

for(int i=0; i<6; i++)

cout<<data[i] <<“,  “;

getch();

}

Berikut adalah contoh program dari insertion sort

Share on Google Plus

About ademahendra

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.