Tambahan Logika Algortima

 Pertemuan 10

Algoritma Merge Sort

Secara literal merge sort berarti mengurutkan dengan cara menggabungkan. Sesuai dengan namanya, algoritma pengurutan merge sort melibatkan penggabungan secara berulang-ulang hingga membentuk rangkaian nilai yang terurut.

Tahap pemecahan 

merupakan tahap divide, menyederhanakan persoalan ke dalam bentuk yang lebih kecil. Pada tahap ini, algoritma merge sort melakukan pemecahan rangkaian nilai (list) menjadi dua bagian (dipecah di tengah) terus menerus hingga hanya tersisa satu elemen pada tiap pecahan. Lihat potongan kode di bawah untuk implementasinya.

Tahap penggabungan

Tahap penggabungan adalah tahap conquer, kebalikan dari proses pemecahan, dimana seluruh potongan yang dihasilkan dari proses pemecahan kemudian digabungkan secara bertingkat.

Pada tahap inilah juga terjadi pengurutan, karena saat digabungkan, masing-masing elemen dari dua potongan yang akan digabung, dibandingkan terlebih dahulu untuk kemudian diletakkan pada sebuah potongan baru sesuai urutan nilainya. Ini berarti bahwa pada masing-masing pecahan yang akan digabungkan, seluruh elemennya sudah terurut dari proses penggabungan sebelumnya.

Kode lengkap

Berikut adalah source code lengkap algoritma merge sort dalam bahasa pemrograman python.

Noted:

Langkah 1: Pembagian Awal

Membagi array menjadi dua bagian:

Langkah 2: Pengurutan Terpisah

Mengurutkan kedua bagian secara terpisah:

Langkah 3: Penggabungan

Menggabungkan kembali kedua bagian yang telah diurutkan:

Algoritma Quick Sort

Algoritma quick sort adalah algoritma pengurutan yang menggunakan proses pemisahan (partitioning) berdasarkan suatu nilai pembatas (pivot) secara berulang-ulang hingga suatu untaian nilai menjadi terurut.

QuickSort adalah salah satu algoritma pengurutan yang efisien dan sering digunakan. Ini menggunakan teknik pembagian dan penaklukkan untuk membagi array menjadi dua bagian, mengurutkan masing-masing bagian secara terpisah, dan kemudian menggabungkannya kembali. Berikut adalah deskripsi umum dan langkah-langkah algoritma QuickSort:

Langkah-Langkah Algoritma QuickSort:

1. Pemilihan Pivot:

   • Pilih elemen dari array sebagai "pivot." Pivot adalah elemen yang akan dibandingkan dengan elemen-elemen lain dalam array.
   • Pilihan pivot dapat dilakukan dengan berbagai cara, misalnya, memilih elemen pertama, terakhir, tengah, atau bahkan secara acak. Pemilihan yang baik dari pivot dapat mempengaruhi kinerja algoritma.

2. Pembagian:

   • Bagi array menjadi dua bagian: elemen-elemen yang lebih kecil dari pivot (bagian kiri) dan elemen-elemen yang lebih besar dari pivot (bagian kanan).
   • Tempatkan pivot pada posisi yang tepat sehingga semua elemen di sebelah kiri lebih kecil dan semua elemen di sebelah kanan lebih besar.

Partitioning

Partitioning adalah sebuah proses untuk membuat sebuah untaian nilai terpisah berdasarkan suatu nilai yang ditetapkan sebagai pembatas (pivot). Hasil dari proses ini adalah seluruh elemen yang nilainya lebih kecil dari pivot ada pada sisi yang berlawanan dengan nilai yang lebih besar dari pivot.

Pada contoh di atas, dilakukan partitioning dengan pivot yang dipilih dari awal elemen (angka 5). Perhatikan bahwa setelah partitioning, seluruh angka yang lebih kecil dari 5 berpindah ke sisi kiri dan sebaliknya. Pada proses ini, tidak ada jaminan bahwa elemen di kanan maupun kiri pivot terurut.

Semoga bermanfaat,

SUMBER REFERENSI

https://koding.alza.web.id/algoritma-merge-sort/

Jawaban Soal No 9 dan 10

Contoh Studi Kasus MergeShort:

25 20 15 3 7 2 1

Langkah 1: Pembagian Awal

Membagi array menjadi dua bagian:

$[25,20,15]\text{dan}[3,7,2,1]$

Langkah 2: Pengurutan Terpisah

Mengurutkan kedua bagian secara terpisah:

$[15,20,25]\text{dan}[1,2,3,7]$

Langkah 3: Penggabungan

Menggabungkan kembali kedua bagian yang telah diurutkan:

$[1,2,3,7,15,20,25]$

Contoh Studi Kasus Quick Short:

Contoh Studi Kasus Quick Short:

Langkah 1: Pemilihan Pivot

Pilih elemen pivot. Misalkan kita pilih elemen pertama sebagai pivot, yaitu 25.

Langkah 2: Pembagian

Pembagian array menjadi dua bagian:

• Bagian kiri dengan elemen yang lebih kecil dari pivot: $[20,15,3,7,2,1]$
• Bagian kanan dengan elemen yang lebih besar dari pivot: $[]$

Tempatkan pivot pada posisi yang tepat: $[20,15,3,7,2,1,25]$

Langkah 3: Rekursi

Terapkan QuickSort rekursif pada kedua bagian array yang dihasilkan setelah pembagian:

• Bagian kiri: $[20,15,3,7,2,1]$

  • Pilih pivot (misalnya, 20).

  • Bagi menjadi bagian kiri: $[15,3,7,2,1]$

  • Bagian pivot: $[20]$

  • Bagian kanan: $[]$

  • Lanjutkan dengan rekursi pada bagian kiri dan kanan.

Langkah 4: Penggabungan

Gabungkan hasil rekursi dengan pivot: $[15,3,7,2,1]+[20]+[]+[25]$

Hasil Akhir:

Array yang terurut: $[1,2,3,7,15,20,25]$

STUDI KASUS:

Buat Langkah Algoritma Merge Short dan Quick Short

[38,27,43,3,9,82,10] setelah diurutkan menjadi [3,9,10,27,38,43,82]

[29,10,14,37,13]  setelah diurutkan menjadi [10,13,14,29,37]

Buat di selembar kertas kumpulkan:

1. Studi Kasus SELECTION SORT:

22, 10, 15, 3, 8, 2.

Langkah-langkah:

1. Langkah 1:

   • Memilih elemen terkecil dari seluruh daftar (2).
   • Menukarnya dengan elemen pertama (22).

   Hasil sementara: [2, 10, 15, 3, 8, 22].

2. Langkah 2:

   • Memilih elemen terkecil dari sisa daftar (3).
   • Menukarnya dengan elemen kedua (10).

   Hasil sementara: [2, 3, 15, 10, 8, 22].

3. Langkah 3:

   • Memilih elemen terkecil dari sisa daftar (8).
   • Menukarnya dengan elemen ketiga (15).

   Hasil sementara: [2, 3, 8, 10, 15, 22].

4. Langkah 4:

   • Memilih elemen terkecil dari sisa daftar (10).
   • Menukarnya dengan elemen keempat (10) (walaupun ini adalah elemen yang sama, kita masih menukarnya untuk memastikan semua elemen sudah terurut).

   Hasil sementara: [2, 3, 8, 10, 15, 22].

5. Langkah 5:

   • Memilih elemen terkecil dari sisa daftar (15).
   • Menukarnya dengan elemen kelima (15) (walaupun ini adalah elemen yang sama, kita masih menukarnya untuk memastikan semua elemen sudah terurut).

   Hasil akhir: [2, 3, 8, 10, 15, 22].

$[10,13,14,29,37]$