Algoritma - Merge Short

Selamat datang kembali di pembelajaran algoritma yang kali ini kita ingin menganalisa suatu algoritma yang terkenal sebagai algoritma pengurutan yang terkenal, yaitu algoritma Merge Sort. Ide yang diambil dari merge sort sama dengan algoritma perhitungan total dengan membagi-bagikan keseluruhan list menjadi komponen kecil lalu mengurutkan komponen-komponen tersebut kemudian menggabungkannya kembali menjadi sebuah list besar. Disini kita memberikan batas atas atau upper bound yang benar-benar tepat secara matematis dan secara tepat juga berapa banyak operasi algoritma merge sort dibutuhkan untuk mengurutkan array masukan dengan benar.

Nah sebelumnya kita sudah melihat sejumlah paradigma desain algoritma umum yang bisa digunakan dalam memecahkan masalah yang melintasi pada aplikasi domain yang berbeda, dan terakhir kita mempelajari algoritma Divide-and-Conquer, yang idenya adalah, Anda mengambil masalah, kemudia memecahnya menjadi sub masalah yang lebih kecil yang kemudian Anda pecahkan atau selesaikan secara rekursif, … … lalu Anda menggabungkan hasil sub-masalah yang lebih kecil tersebut untuk mendapatkan solusi untuk masalah asli yang sebenarnya.

Dan Merge Sort masih merupakan bagian dari algoritma Divide-and-Conquer dewasa ini, yang mungkin paling transparan, dan akan menunjukkan dengan jelas apa paradigmanya, analisis dan tantangan apa yang disajikan, dan jenis apa manfaat yang mungkin Anda peroleh. Algoritma merge sort secara simplenya adalah barisan data dibagi menjadi dua subbarisan. Kemudian Sort secara rekursif. Lalu Gabung hasil langkah 2 dari 2 subbarisan yang terurut menjadi barisan yang terurut.

Namun harus diingat ketika materi algoritma Divide-and-Conquer kita memberi contoh pembagian masalah dengan 2 sub masalah saja, sedang pada Algoritma merge sort ini nantinya Proses pembagian data dilakukan secara rekursif sehingga datanya nanti tidak dapat dibagi lagi atau maksudnya data dalam sub bagian menjadi tunggal.

Setelah data tidak dapat dibagi lagi, proses penggabungan atau merging dilakukan antara sub-sub bagian masalah dengan memperhatikan urutan data yang diinginkan atau ascending/kecil ke besar atau descending/besar ke kecil. Proses penggabungan kemudian dilakukan sampai semua data tergabung serta terurut sesuai urutan yang diiginkan. Kompleksitas algoritma merge sort adalah O(n log n).

Kita nantinya akan melakukan analisis Merge Sort menggunakan apa yang disebut sebagai metode “Recursion-Tree”. Jadi ini adalah cara mengikat jumlah total operasi yang dijalankan oleh suatu algoritma. Dan seperti yang akan kita lihat nanti, metode Recursion-Tree ini sangat populer. Dan itu akan memungkinkan kita untuk menganalisis banyak algoritma rekursif yang berbeda, banyak algoritma Divide-and-Conquer yang berbeda, termasuk algoritma penggandaan bilangan bulat yang kita diskusikan dalam segmen sebelumnya. Jadi itulah alasan untuk memulai dengan Merge Sort. Jadi Sort Merge adalah tujuannya dalam hidup adalah untuk mengurutkan array input yang diberikan. Jadi itu akan bertelur, atau menyebut dirinya pada susunan yang lebih kecil. Dan ini akan menjadi aplikasi Divide-and-Conquer kanonis, di mana kita hanya mengambil array input, kita membaginya menjadi setengah, kita memecahkan setengah kiri secara rekursif, kita memecahkan setengah kanan secara rekursif, dan kemudian kita menggabungkan hasilnya.

Untuk memahami merge sort, kami mengambil array yang tidak disortir sebagai berikut –

images1

Kita tahu bahwa merge sort pertama kali membagi seluruh array secara iteratif ke dalam bagian yang sama kecuali jika nilai-nilai atom tercapai. Kita lihat di sini bahwa array 8 item dibagi menjadi dua array dengan ukuran 4.

images2

Ini tidak mengubah urutan penampilan item dalam aslinya. Sekarang kita membagi dua susunan menjadi dua bagian.

images3 Kita selanjutnya membagi array ini dan kami mencapai nilai atom yang tidak dapat dibagi lagi ..

images4 Sekarang, kami menggabungkannya dengan cara yang persis sama seperti yang dipecah. Harap perhatikan kode warna yang diberikan ke daftar ini.

Kita pertama membandingkan elemen untuk setiap daftar dan kemudian menggabungkannya ke daftar lain dengan cara yang disortir. Kita melihat bahwa 15 dan 34 berada dalam posisi yang disortir. Kami membandingkan 28 dan 10 dan dalam daftar target 2 nilai yang kami masukkan 10 pertama, diikuti oleh 28. Kita mengubah urutan 19 dan 35 sedangkan 43 dan 44 ditempatkan secara berurutan.

images5

Pada iterasi berikutnya dari fase penggabungan, kami membandingkan daftar dua nilai data, dan menggabungkannya ke dalam daftar nilai data yang ditemukan, menempatkan semua dalam urutan yang diurutkan.

images6

Setelah penggabungan akhir, daftar akan terlihat seperti ini –

images7

Sekarang kita harus mempelajari beberapa aspek program penggabungan gabungan.

Maka Algoritmanya: Gabungkan sortir terus membagi daftar menjadi dua bagian yang sama sampai tidak dapat dibagi lagi. Menurut definisi, jika hanya satu elemen dalam daftar, itu diurutkan. Kemudian, gabungkan semacam menggabungkan daftar yang disortir lebih kecil dengan membuat daftar baru disortir juga.

Sekarang kita harus mempelajari beberapa aspek program penggabungan gabungan.

  • Langkah 1 - jika hanya satu elemen dalam daftar itu sudah diurutkan, kembali.
  • Langkah 2 - bagilah daftar secara rekursif menjadi dua bagian hingga tidak dapat dibagi lagi.
  • Langkah 3 - menggabungkan daftar yang lebih kecil ke dalam daftar baru dalam urutan terurut.

Implementasi merge sort dapat anda pelajari berikut ini:

#include <stdio.h>
#include <stdlib.h>
void mergesort(int key[],int n);
void merge(int a[],int b[],int c[],int m, int n);
int main(void){
int i, key[8]={15,34,28,10,35,19,43,45};
mergesort(key,8);
for(i=0;i<8;++i)
printf("%d\t",key[i]);
return 1;
}
void mergesort(int key[], int n){
int j,k,m,*w;
for (m=1;m<n;m*=2);
if (m!=n){
printf("jumlah arraynya salah ");
exit(1);
}
w = calloc(n,sizeof(int));
assert(w!=NULL);
for (k=1;k<n;k*=2){
for(j=0;j<n-k;j+=2*k)
merge(key+j,key+j+k,w+j,k,k);
for(j=0; j<n; ++j)
key[j]=w[j];
}
free(w);
}
void merge(int a[],int b[],int c[],int m,int n){
int i=0,j=0,k=0;
while (i < m && j < n)
if (a[i] < b[j])
c[k++] =a[i++];
else
c[k++] =b[j++];
while (i<m)
c[k++] =a[i++];
while (j<n)
c[k++] =b[j++];
}

Dimateri berikutnya kita akan membahas analisa merge sort dengan pseucodenya.Terima kasih.