Urut gabung: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k {{rapikan}} |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.2 |
||
(37 revisi perantara oleh 25 pengguna tidak ditampilkan) | |||
Baris 1:
[[Berkas:Merge sort animation2.gif|jmpl|200px|contoh penggambaran cara kerja merge sort.]]'''Urut gabung''' atau sering juga disebut dalam istilah [[bahasa Inggris|Inggrisnya]] '''merge sort''' merupakan algoritme 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. Algoritme ini ditemukan oleh John von Neumann pada tahun 1945.
== Algoritme ==
Prinsip utama yang diimplementasikan pada algoritme urut gabung sering kali disebut sebagai ''pecah-belah dan taklukkan'' ([[bahasa Inggris]]: ''divide and conquer''). Cara kerja algoritme urut gabung adalah membagi [[larik]] data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan [[notasi O besar|O]](nlog(n)). Dalam bentuk [[pseudocode]] sederhana algoritme ini dapat dijabarkan sebagai berikut:
# Original data is on the input tape; the other tapes are blank
'''function''' merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
'''while''' any records remain on the input_tape
'''while''' any records remain on the input_tape
merge( input_tape, output_tape, scratch_tape_C)
merge( input_tape, output_tape, scratch_tape_D)
'''while''' 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 ...)
'''function''' merge(left[], right[], output_tape[])
'''do'''
'''if''' left[current] ≤ right[current]
append left[current] to output_tape
read next record from left tape
'''else'''
append right[current] to output_tape
read next record from right tape
'''while''' left[current] < left[next] '''and''' right[current] < right[next]
'''if''' left[current] < left[next]
append current_left_record to output_tape
'''if''' right[current] < right[next]
append current_right_record to output_tape
'''return'''
Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan '''''{3, 9, 4, 1, 5, 2}''''' adalah sebagai berikut:
* Larik tersebut dibagi menjadi dua bagian, '''''{3, 9, 4}''''' dan '''''{1, 5, 2}'''''
* Kedua larik kemudian diurutkan secara terpisah sehingga menjadi '''''{3, 4, 9}''''' dan '''''{1, 2, 5}'''''
* Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut '''''{1}''''', sementara nilai-nilai dalam masing larik '''''{3, 4, 9}''''' dan '''''{2, 5}''''' (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)
* langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik 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}'''''
== Pranala luar ==
{{wikibooks|Algorithm implementation|Sorting/Merge_sort|Merge sort}}
* {{en}} [http://www.sorting-algorithms.com/merge-sort Animated Sorting Algorithms: Merge Sort] – graphical demonstration and discussion of array-based merge sort
* {{en}} [http://tide4javascript.com/?s=Merge Analyze Merge Sort in an online Javascript IDE]
* {{en}} [http://www.atkinson.yorku.ca/~sychen/research/sorting/sortingHome.html Merge sort applet] {{Webarchive|url=https://web.archive.org/web/20090228175036/http://www.atkinson.yorku.ca/~sychen/research/sorting/sortingHome.html |date=2009-02-28 }} with [[Tree traversal|level order]] recursive calls to help improve algorithm analysis
* {{en}} [http://www.nist.gov/dads/HTML/mergesort.html Dictionary of Algorithms and Data Structures: Merge sort]
* {{en}} [http://www.rosettacode.org/wiki/Merge_sort Implementation of merge sort in various languages] on Rosetta Code
* {{en}} [http://en.literateprograms.org/Category:Merge_sort Literate implementations of merge sort in various languages] {{Webarchive|url=https://web.archive.org/web/20090618083928/http://en.literateprograms.org/Category:Merge_sort |date=2009-06-18 }} on LiteratePrograms
* {{en}} [http://www.algorithmist.com/index.php/Merge_sort Implementation for C++]
* {{en}} [http://coderaptors.com/?MergeSort A colored graphical Java applet] {{Webarchive|url=https://web.archive.org/web/20110708174304/http://coderaptors.com/?MergeSort |date=2011-07-08 }} which allows experimentation with initial state and shows statistics
* {{en}} [http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Simon Tatham's explanation and code for a merge sort]
* {{en}} [http://www.mycstutorials.com/articles/sorting/mergesort MergeSort tutorial and Java code for beginners] {{Webarchive|url=https://web.archive.org/web/20110714142249/http://www.mycstutorials.com/articles/sorting/mergesort |date=2011-07-14 }}
* {{en}} [http://talkera.org.cp-in-1.webhostbox.net/wp/?p=95 MergeSort in Java, Python, Perl, PHP, Ruby] {{Webarchive|url=https://web.archive.org/web/20140608001032/http://talkera.org.cp-in-1.webhostbox.net/wp/?p=95 |date=2014-06-08 }}
[[Kategori:Algoritme pengurutan]]
|