Merge Sort Menggunakan Bahasa Pemrograman C

17:38 Pemrograman Web 7 Comments






Merge sort adalah algoritma pengurutan data dalam ilmu komputer yang dibuat untuk kebutuhan pengurutan rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar.
Merge Sort berfungsi untuk mengurtkan nilai yang belum terurut dengan menggunakan metode Merge Sort, untuk lebih jelasnya metode pengurutan data menggunakan Merge Sort adalah sebagi berikut.
Berikut penjelasan langkah kerja dari Merge sort. Langkah kerja merge sort terbagi atas 3 bagian yaitu:

Divide: Jika array A yang diberikan memiliki nilai nol atau satu elemen, langsung dikembalikan; itu sudah diurutkan. Jika tidak, akan dilakukan pembagi A [p .. r] menjadi dua subarrays A [p .. q] dan A [q + 1 .. r], masing-masing berisi sekitar setengah dari elemen A [p .. r]. Artinya, q adalah titik tengah dari A [p .. r].

Conquer: dipencahkan menjadi dua subarrays A [p .. q] dan A [q + 1 .. r]. Dan memberi solusi pada setiap bagian dengan memanggil prosedur merge sort.

Combine: Menggabungkan elemen A [p .. r] dengan menggabungkan dua subarrays diurutkan A [p .. q] dan A [q + 1 .. r] menjadi urutan yang berurut.

Kita membutuhkan kasus dasar. Kasus dasar adalah subarray yang mengandung kurang dari dua unsur, yaitu, ketika p \ GEQ rp≥r, sejak subarray tanpa unsur atau hanya satu elemen sudah diurutkan. Jadi kita akan devide-conquer-combine hanya ketika p <rp <r.

Berikut adalah contohnya.
Contohnya kita mempunya array yang berisi  [14, 7, 3, 12, 9, 11, 6, 2], sehingga subarray pertama sebenarnya adalah array penuh, array [0..7] (p = 0p = 0 dan r = 7R = 7). Subarray ini memiliki setidaknya dua elemen, dan itu bukan kasus dasar.
Dalam membagi langkah, kita menghitung q = 3q = 3.
Langkah conquer kita memilah dua subarrays array [0..3], yang berisi [14, 7, 3, 12], dan array [4..7], yang berisi [9, 11, 6, 2]. Ketika kami kembali dari langkah conquer, masing-masing dua subarrays diurutkan: array [0..3] berisi [3, 7, 12, 14] dan array [4..7] berisi [2, 6, 9, 11], sehingga array penuh [3, 7, 12, 14, 2, 6, 9, 11].
Dan yang terakhir, menggabungkan langkah- langkah sebelumnya yaitu menggabungkan dua subarrays diurutkan di bagian pertama dan bagian kedua, dan akan menghasilkan [2, 3, 6, 7, 9, 11, 12, 14].

Bagaimana array subarray [0..3] menjadi berurutan? Cara yang sama. Ini memiliki lebih dari dua unsur, dan itu bukan kasus dasar. Dengan p = 0p = 0 dan r = 3r = 3, menghitung q = 1Q = 1, rekursif mengurutkan array [0..1] ([14, 7]) dan array [2..3] ([3, 12] ), sehingga array [0..3] mengandung [7, 14, 3, 12], dan menggabungkan babak pertama dengan babak kedua, memproduksi [3, 7, 12, 14].
Bagaimana array subarray [0..1] menjadi berurutan? Dengan p = 0p = 0 dan r = 1r = 1, menghitung q = 0q = 0, rekursif mengurutkan array [0..0] ([14]) dan array [1..1] ([7]), sehingga array [0..1] masih mengandung [14, 7], dan menggabungkan babak pertama dengan babak kedua, memproduksi [7, 14].


Jadi Algoritmanya yaitu:
Merge Sort terus membagi array menjadi dua bagian yang sama sampai tidak ada lagi yang bias dibagi. Menurut definisi, jika hanya salah satu unsur dalam daftar, yang diurutkan. Kemudian Merge Sort menggabungkan (combine) menjadi terbentuk sort yang baru.

Langkah 1 - jika hanya salah satu unsur dalam daftar itu sudah diurutkan, kembali.
Langkah 2 - membagi daftar rekursif menjadi dua bagian sampai tidak ada lagi yang bias dibagi.
Langkah 3 - menggabungkan daftar yang lebih kecil ke dalam daftar baru untuk disortir.


 Link Github : Merge Sort

Nama: Ayu Anggara
NPM: 1144014

7 komentar: