pengertian insertion sort dan marge sort pada java beserta contoh

INSERTION SORT

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).
Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.

Demikian juga halnya dalam pengurutan data.
Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.
Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

Berikut adalah simulasi Algoritma Insertion Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Contoh Insertion Sort :

• Bagian biru/abu-abu (dua bilangan pertama) sekarang dalam keadaan terurut secara relatif.

Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke dalam bagian biru/abu-abu sehingga
setelah penyisipan tersebut, bagian biru/abu-abu tetap dalam keadaan terurut secara relatif;
CARANYA :
pertama : Ambil bilangan ketiga (4).

• Kedua : Geser bilangan kedua (10) shg ada ruang untuk disisipi.

• Ketiga : Sisipkan bilangan 4 ke posisi yang tepat

• Sekarang, tiga bilangan pertama sudah terurut secara relatif dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tsb.  Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut secara relatif.

•  Ulangi proses tsb sampai bilangan terakhir disisipkan

•  Proses Sorting Selesai

atau agar lebih jelas dapat dilihat pada video 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.

 import java.util.Scanner;
public class Insertion {
      public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
   System.out.print("Banyak data : ");
   int N = in.nextInt();
   int data[] = new int[N];
   for(int i=0; i<N; i++){
      System.out.print("data ke-"+(i+1)+" : ");
      data[i] = in.nextInt();
   }
   //prose isertion sort
   for(int i=1; i<data.length; i++){
      int key = data[i];
      int j=i;
      while(j >0 && data[j-1]>key){
          data[j]=data[j-1];
          j--;
      }
      data[j]=key;
   }
   //hasil pengurutan
   System.out.print("Data yang telah urut : ");
   for(int i=0; i<data.length; i++){
       System.out.print(data[i]+" ");
   }
   System.out.println();


    }
   
}

MARGE SORT

MergeSort adalah metode pengurutan data dengan cara data dibagi menjadi subkumpulan - subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging

Algoritma pengurutan data mergesort dilakukan dengan menggunakan cara divideandconquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode mergesort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Mergesort.

1.   Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2.   Conquer
Conquer setiap bagian dengan memanggil prosedur mergesortsecararekursif

3.    Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkanrangkaian 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.

Contoh penerapan atas sebuah larik/array sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:

a.       pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}

b.      Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}

c.       Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)

d.      langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya

e.       {1, 2} ↔{3, 4, 9} dan {5}

f.       {1, 2, 3} ↔ {4, 9} dan {5}

g.      {1, 2, 3, 4}↔{9} dan {5}

h.      {1, 2, 3, 4, 5}↔{9} dan {null}

i.        {1, 2, 3, 4, 5, 9}↔{null}dan {null}

a

 atau agar lebih jelas dapat dilihat pada video berikut 

Contoh program sedehana mergesort

Public class mergeSort{

Public static void main(String args [ ] ){

int i;

int array [ ] = {7,5,1,3,6,4,9,8};

System.out.println("\n\n Kelompok 3\n\n");

System.out.println(" Pengurutan dengan MergeSort\n\n");

System.out.println("Data Sebelum Diurutkan:\n");

    for(i = 0; i < array.length; i++)

System.out.print( array[i]+"  ");

System.out.println( );

Merge Sort_srt(array,0, array.length - 1);

System.out.print("Data Setelah Diurutkan:\n");

    for(i = 0; i < array.length; i++)

System.out.print(array[i]+"  ");

System.out.println();

    }

Public static void mergeSort_srt(int array[ ],int lo, int n){

 int low = lo;

int high = n;

if (low > = high)

    {return; }

int middle = (low + high) / 2;

mergeSort_srt(array, low, middle);

mergeSort_srt(array, middle + 1, high);

int end_low = middle;

int start_high = middle + 1;

while ((lo <= end_low) && (start_high <= high))

    {

if (array[low] < array[start_high]) {

low++; }

else {

int Temp = array[start_high];

            for (int k = start_high- 1; k > =low; k--) 

                {array[k+1] = array[k]; }

array[low] = Temp;

low++;

end_low++;

start_high++;  }

        }

    }