Merge Sort

29 11 2010

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai divide and conquer. Cara kerja algoritma merge sort adalah membagi Array data yang diberikan menjadi dua bagian yang lebih kecil. Kedua array yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk array baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O (nlog(n)). Dalam bentuk pseudocode sederhana algoritma ini dapat dijabarkan sebagai berikut:

<pre> # Original data is on the input tape; the other tapes are blank
 <strong>function</strong> merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
     <strong>while</strong> any records remain on the input_tape
         <strong>while</strong> any records remain on the input_tape
             merge( input_tape, output_tape, scratch_tape_C)
             merge( input_tape, output_tape, scratch_tape_D)
         <strong>while</strong> any records remain on C or D
             merge( scratch_tape_C, scratch_tape_D, output_tape)
             merge( scratch_tape_C, scratch_tape_D, input_tape)

 # take the next sorted chunk from the input tapes, and merge into the single given output_tape.
 # tapes are scanned linearly.
 # tape[next] gives the record currently under the read head of that tape.
 # tape[current] gives the record previously under the read head of that tape.
 # (Generally both tape[current] and tape[previous] are buffered in RAM ...)
 <strong>function</strong> merge(left[], right[], output_tape[])
     <strong>do</strong>
        <strong>if</strong> left[current] ≤ right[current]
            append left[current] to output_tape
            read next record from left tape
        <strong>else</strong>
            append right[current] to output_tape
            read next record from right tape
    <strong>while</strong> left[current] < left[next] <strong>and</strong> right[current] < right[next]
    <strong>if</strong> left[current] < left[next]
        append current_left_record to output_tape
    <strong>if</strong> right[current] < right[next]
        append current_right_record to output_tape
    <strong>return</strong>
<strong>


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

  • Arrray tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
  • Kedua array kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
  • Sebuah array baru dibentuk yang sebagai penggabungan dari kedua array tersebut {1}, sementara nilai-nilai dalam masing array {3, 4, 9}dan {2, 5} (nilai 1 dalam elemen array ke dua telah dipindahkan ke array baru)
  • langkah berikutnya adalah penggabungan dari masing-masing array ke dalam array baru yang dibuat sebelumnya.
    • {1, 2} <-> {3, 4, 9} dan {5}
    • {1, 2, 3} <-> {4, 9} dan {5}
    • {1, 2, 3, 4} <-> {9} dan {5}
    • {1, 2, 3, 4, 5} <-> {9} dan {null}
    • {1, 2, 3, 4, 5, 9} <-> {null} dan {null}


 


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: