Algoritma - Analisa Struktur Pohon Merge Sort dan Merge Sort Pseudocode

Kita sudah membahas pada materi sebelumnya bagaimana Merge Sort itu berkerja. Dan nampaknya dari pembahasan tersebut memberikan analisis running time dari algoritma merge sort Secara khusus akan memperkuat klaim bahwa teknik rekursif dengan divide dan conquer merge sort itulah yang terbaik karena memiliki kinerja yang lebih baik daripada algoritme pengurutan sederhana yang mungkin Anda ketahui,diantaranya adalah insertion sort, selection sort atau bubble sort. Bahkan kita sudah melihat bahwa untuk mengurutkan susunan N angka, maka algoritma merge sort membutuhkan tidak lebih dari waktu yang konstan n log dalam operasi. Maka dapat diklaim bahwa Running Time Merge Sort untuk setiap input susunan N angka, merge sort menghasilkan array ouput yang diurutkan dan menggunakan paling banyak operasi 6n log2 n + 6n

Pembuktian klaim ini bisa dilakukan dengan menggunakan metode pohon rekursi. Gagasan metode pohon rekursi adalah dengan meulis seluruh pekerjaan yang dilakukan oleh algoritme merge sort secara rekursif dalam struktur pohon dengan anak-anak dari node yang diberikan sesuai dengan panggilan rekursif yang dibuat oleh node tersebut. Inti dari struktur pohon ini adalah akan memfasilitasi cara menarik untuk dihitung secara up keseluruhan pekerjaan yang dilakukan oleh algoritma dan akan sangat memudahkan analisis.

Kita akan melihat struktur pohon dari merge sort ini. Awalnya berada pada level 0 untuk melakukan merge sort. Kemudian struktur pohon ini akan menjadi biner dimana metode merge sort melakukan dua rekursive calls/panggilan rekursif. Pada root dari struktur pohon semua input data atau masalah umumnya terletak disana. Kemudian pada level 1 kita punya sub masalah yang dibagi menjadi sebelah kiri dan kanan.

images1

Pada level 2, tentu saja, masing-masing terdapat dua lagi panggilan rekursif tingkat satu ini akan sendiri membuat dua panggilan rekursif. Setiap operasi sudah pada seperempat dari array input asli. Jadi itu adalah level dua rekursif panggilan yang ada empat. Dan proses ini akan berlanjut hingga pada akhirnya, rekursi akan berakhir dalam kasus dasar ketika hanya ada array ukuran nol atau satu.

Jadi Yang ada di bagian bawah rekursi ini sesuai dengan kasus dasar, dengan membuat fungsi n, panjang dari array input bisa di persamakan dengan log2 n atau binary logaritma.

images2

Begitu juga dengan jumlah level dari pohon rekursi pada dasarnya logaritmik dalam ukuran array input. Alasannya pada dasarnya bahwa ukuran input dikurangi oleh faktor dua dengan setiap tingkat rekursi. Jika Anda memiliki ukuran input n di tingkat luar, kemudian masing-masing set panggilan rekursif pertama beroperasi larik ukuran n lebih dari 2. Pada tingkat dua, setiap larik memiliki ukuran n lebih dari 4 dan seterusnya, sedangkan jika rekursi keluar, baik, ke bawah pada kasus dasar, di mana tidak ada lagi rekursi, yang merupakan tempat masukan larik memiliki ukuran satu atau kurang. Jadi dengan kata lain, jumlah level rekursi adalah berapa kali tepatnya Anda perlu membagi n dengan 2, sampai Anda turun ke angka yang tidak bisa dibagi lagi

Dan ingat, itulah definisi dari basis 2n logaritma. Jadi sejak level pertama adalah level nol dan level terakhir adalah level log2 n. Jumlah total level sebenarnya log2 n + 1. Dan ketika saya menuliskan di sini dengan asumsi bahwa n adalah fungsi pangkat 2 yang bukan masalah besar.

Maksud saya, analisis biasanya diperpanjang untuk kasus di mana n bukan funggsi pangkat 2. Tetapi dengan cara ini kita tidak perlu berpikir tentang pecahan log2 n yang kemudian merupakan integer. Jadi sekali lagi, di bagian bawah dari pohon itu, kita punya daunnya. Dan Kasus dasar, dimana tidak ada rekursi lagi. Yang mana, ketika n adalah fungsi pangkat 2, bersesuaian tepat untuk elemen array tunggal. Jadi itulah pohon rekursi yang sesuai dari MergeSort. Dan kita akan melihat itu khususnya cara mudah untuk memperhitungkan semua garis yang berbeda kode yang dieksekusi. Oke, jadi mari kita lanjutkan pembahasan pseudo-code untuk algoritma ini. Sekarang kita akan melihat pseudocode untuk menggabungkan fungsi pengurutan. Karena algoritme kami menunjukkan dua fungsi utama - bagikan & gabungkan.

Merge soprt pseudo-code disini, menyisihkan dengan tepat bagaimana subroutine penggabungan diimplementasikan. Dan dengan demikian, tingkat tinggi harus sangat sederhana dan jelas pada titik ini. Begitu akan ada dua panggilan rekursif, dan kemudian akan ada langkah penggabungan. Bisa anda lihat contoh berikut:

function mergesort(m)
    var list left, right
    if length(m) ≤ 1
        return m
    else
        middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)
        result = merge(left, right)
        return result

atau contoh berikut:

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c

end procedure