Coretan BoWo Coretan BoWo Coretan BoWo: Mengenal Teknik Marge Sort

Sunday, May 13, 2012

Mengenal Teknik Marge Sort

Dalam ilmu komputer, menggabungkan semacam atau mergesortadalah algoritma sorting untuk mengatur ulang daftar (atau struktur data lain yang hanya dapat diakses secara berurutan, misalnya file stream) ke dalam urutan tertentu. Ini adalah contoh yang baik terutama membagi dan menaklukkan paradigma algoritmik. Ini adalah semacam perbandingan.

Secara konseptual, menggabungkan bekerja seperti sebagai berikut:
1. Bagilah daftar disortir menjadi dua sublists sekitar setengah ukuran
2. Urutkan masing-masing dua sublists
3. Menggabungkan dua disortir sublists kembali ke salah satu daftar diurutkan.

Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.
Isi
[hide]
• 1 Implementasi
o 1,1 Pseudocode
o 1,2 Ada
o 1,3 Jawa
o 1,4 Haskell
o 1,5 Jawa
o 1,6 Common Lisp
o 1,7 Miranda
o 1,8 OCaml
o 1,9 PHP
o 1,10 Prolog
o 1,11 Python
o 1,12 Ruby
o 1,13 Skema
o 1,14 Seed7
o 1,15 Fortran
o 1,16 JavaScript
• 2 Analisis
• 3 Mengoptimalkan menggabungkan semacam
• 4 Perbandingan dengan algoritma jenis lainnya
• 5 Utility pada pemilahan online
• 6 Pranala luar
• 7 Sumber

[sunting] Implementasi
[sunting] Pseudocode
fungsi mergesort (m)
var daftar kiri, kanan
jika panjang (m) ≤ 1
kembali m
lain
panjang = tengah (m) / 2
untuk setiap x dalam m sampai dengan tengah menambahkan x ke kiri
untuk setiap x dalam m setelah menambahkan x menengah ke kiri kanan = mergesort (kiri) kanan = mergesort (kanan) hasil = merge (kiri, kanan)
mengembalikan hasil
Ada beberapa varian untuk digabung () fungsi, varian yang paling sederhana bisa terlihat seperti ini:
fungsi merge (kiri, kanan)
var daftar hasil
sementara panjang (kiri)> 0 dan panjang (kanan)> 0
jika pertama (kiri) ≤ pertama (kanan) append pertama (kiri) untuk hasil sisa kiri = (kiri)
lain
append pertama (kanan) untuk hasil yang tepat = sisanya (kanan)
jika panjang (kiri)> 0 menambahkan kiri untuk hasil
jika panjang (kanan)> 0 menambahkan hak untuk hasil
kembali hasil
[sunting] Ada
Ada implementasi Data_T menggunakan tipe data array.
fungsi Mergesort (Data: di Data_T) Data_T kembali adalah mulai jika <= Data'Length 1 kemudian kembali data; lain menyatakan Tengah: Integer: = (Data'First + Data'Last) / 2; Waktu: Data_T: = Data (Data "Pertama .. Tengah); Kanan: Data_T: = Data (Tengah + 1 .. Data'Last); mulai Waktu: = Mergesort (Waktu); Kanan: = Mergesort (Kanan); kembali Gabung (Kiri, Kanan); akhir , jika; akhir akhir Mergesort;
Definisi dari Merge fungsi:
fungsi Merge (Waktu: Data_T; Kanan: Data_T) Data_T kembali adalah Hasil: Data_T (1 .. Left'Length + Right'Length); L: Integer: = Left'First; R: Integer: = Right'First; I: integer: = Result'First; mulai saat L <= Left'Last dan R <= loop Right'Last jika Waktu (L) <= Kanan (R) maka Hasil (I): = Kiri (L); L: = L + 1; I: = I + 1; Hasil lain (I): = Right (R); R: 1 R + =; I: I + 1; end = jika; loop akhir, jika L <= Left'Last lalu Hasil (I.. Result'Last): = Waktu (L.. Left'Last); berakhir jika, jika R <= Right'Last lalu Hasil (I.. Result'Last) ': = Right (kanan R.. terakhir); akhir jika; Hasil kembali; akhir Merge;
[sunting] C
/ / Mix dua diurutkan tabel dalam satu dan membagi hasilnya ke dalam dua meja. Int * Mix (* int tab1, * int tab2, int count1, int count2) (int i, I1, i2; i = I1 = i2 = 0 ; int * temp = (* int) malloc (sizeof (int) * (count1 + count2)), sedangkan ((I1 [sunting] Haskell
seperti:: Ord a => [a] -> [semacam []] =] semacam [[x] = [x xs semacam] = menggabungkan (semacam YS) (ZS semacam) di mana (YS, ZS) = splitAt ( panjang xs `div` 2) xs menggabungkan [y] = y menggabungkan x [] = x menggabungkan (x: xs) (y: YS) | x <= y = x: merger xs (y: YS) | dinyatakan = y : merger (x: xs) YS
[sunting] Jawa

/ / Hanya melihat hal ini secara lebih, ringkas cara sederhana tanpa komentar
int publik [] mergeSort (int array[]) (
jika(array). panjang> 1 (int elementsInA1 = array. panjang / 2; int elementsInA2 = array. panjang - elementsInA1; int arr1 [] = int baru [elementsInA1]; int arr2 [] = [int baru elementsInA2];

untuk(i int 0 = i untuk(int i elementsInA1 =; i
sementara(arr1.length! = j & & arr2.length! = k) (
jika(arr1 [j] <= arr2 [k]) (
arrayi] [= arr1 [] j; i + +; j + +;)
lain
(
array[i] = arr2 k []; i + +; k + +;))

sementara(arr1.length! = j) (
array[i] = arr1 [j]; i + +; j + +;)
sementara(arr2.length! = k ) (
array[i] = arr2 k []; i + +; k + +;))

/ / mengembalikan array diurutkan ke pemanggil fungsi
return array;) Sumber: http [:/ / www.mycsresource.net / artikel / pemrograman / sorting_algos / mergesort MyCSResource.net]
[sunting] Common Lisp
;;; 


Fungsi Helper untuk memberitahu kami jika urutan yang diberikan hanya memiliki satu elemen. (Defun tunggal (urutan) (jika (urutan consp) (tidak (urutan CDR)) (= (urutan panjang) 1)));;; Sequence bisa menjadi vektor atau daftar. Catatan bahwa ini berarti bahwa ini;;; kode tidak dioptimalkan untuk semua itu semacam. (Defun menggabung-(urutan) (jika (atau (urutan null) (urutan tunggal)) urutan (membiarkan ((setengah (truncate (/ (urutan panjang) 2))));; gabungan fungsi umum-cadel standar, yang tidak adil;; apa yang kita inginkan. (gabungan (tipe-urutan) (menggabung-macam (subseq urutan 0 setengah)) (menggabung -jenis (separuh subseq urutan)) #'<))))
[sunting] Miranda

semacam [] = [] mengurutkan [x] = [x] = array gabungan semacam (semacam kiri) (kanan semacam) mana kiri = [array! | y [sunting] OCaml

Fungsi untuk menggabungkan sepasang daftar diurutkan:
# Biarkan rec menggabungkan = | daftar fungsi, [] | [], daftar - daftar> | h1:: t1, h2:: t2 -> jika h1 <= h2 maka h1:: merger (t1, h2:: t2) lain h2:: merger (h1:: t1, t2);; menggabungkan val: 'a * list' daftar -> 'daftar =
Fungsi ini termasuk dalam stdlib OCaml sebagai List.merge tetapi juga dimasukkan di sini untuk daftar kejelasan. Fungsi untuk mengurangi separuh:
# Biarkan rec membagi dua = fungsi | [] | [_] sebagai t1 -> t1, [] | h:: t -> biarkan t1, t2 = membagi dua t h:: t2, t1;; membagi dua val: 'daftar -> 'a * list' daftar =
Fungsi untuk menggabungkan daftar semacam:
# Biarkan merge_sort rec = fungsi | [] | [_] sebagai daftar - daftar daftar |> -> biarkan l1, l2 = membagi daftar dalam menggabungkan (merge_sort l1, l2 merge_sort);; semacam val: 'daftar ->' a daftar =
Sebagai contoh:
# Merge_sort [6; 7; 0; 8; 3; 2; 4; 9; 5; 1];; -: int list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
[sunting] PHP

fungsi merge_sort (& $ arrayToSort) (if (sizeof ($ arrayToSort) <= 1) return $ arrayToSort; / / split array masukan kami menjadi dua bagian / / kiri ... $ leftFrag = array_slice ($ arrayToSort, 0, (int ) (count ($ arrayToSort) / 2)); / / kanan ... $ rightFrag = array_slice ($ arrayToSort, (int) (count ($ arrayToSort) / 2)); / / rekursi / / membelah dua bagian ke memperdua masing-masing ... $ leftFrag = merge_sort ($ leftFrag); $ rightFrag = merge_sort ($ rightFrag); $ returnArray = merge ($ leftFrag, $ rightFrag); return $ returnArray;) fungsi penggabungan (& $ LF, & $ rF) ($ hasil = array (); / / sedangkan kedua array memiliki sesuatu yang mereka sementara (count ($ LF)> 0 & & count ($ rF)> 0) (if ($ LF [0] <= $ rF [ 0]) (array_push ($ hasil, array_shift ($ LF));) else (array_push ($ hasil, array_shift ($ rF));)) / / tidak melihat ini dalam kode pseudo, / / tapi perlu menjadi sebagai salah satu array / / bisa menjadi kosong sebelum array_splice lain ($ hasil, count ($ hasil), 0, $ LF); array_splice ($ hasil, count ($ hasil), 0, $ rF); return $ hasil ;)
[sunting] Prolog

Ini merupakan implementasi ISO-Prolog kompatibel merge semacam dengan pengecualian predikat tambahkan / 3 dan panjang / 2 yang, sementara tidak ditentukan oleh standar ISO, yang tersedia di hampir semua implementasi Prolog.
% Merge-Urut: ms (+ Sumber,? Hasil) ms (Xs, Rs): - panjang (Xs, L), (L = <2 -> Rs = ys; Split adalah L / / 2, panjang (Front0, Split), append (Front0, Back0, Xs), ms (Front0, Front), ms (Back0, Kembali), menggabungkan (Front, Back, Rs)):.% Gabung daftar merge (+ List1, + List2, - Hasil) menggabungkan ([], ys, ys): -)!. menggabung (Xs, [], ys: -!. menggabungkan ([X | Xs], [Y | Ys], Zs): - (X @ = Zs = [X | Rest], menggabungkan (Xs, [Y | Ys], Istirahat); Zs = [Y | Rest], menggabungkan ([X | Xs], Ys, Istirahat)).

[sunting] Python
def semacam (array): jika len (array) <1 =: array kembali pertengahan = len (array) / / 2 kembali merge (semacam (array [0: pertengahan]), mengurutkan (array [pertengahan:])) # ini mungkin bukan yang paling menyeluruh idiomatic python, atau paling efisien menggabungkan # (itu duplikat data bila "Mengirimkan") # tetapi bekerja def merge (kiri, kanan): merger = [] i = 0 j = 0 len sementara (yang telah bergabung ) Kendali implementasi:
def mergesort (n): "" "Secara rekursif mengurutkan daftar menggabungkan daftar. Pengembalian mengurutkan." "" depan = [n: len (n) / 2] kembali len = n [(n) / 2:] bila len ( depan)> 1: depan = mergesort (depan) jika len (kembali)> 1: kembali = mergesort (belakang) kembali bergabung (depan, belakang) def menggabung (depan, belakang): "" "Gabungkan dua diurutkan daftar bersama-sama. Barang daftar digabung "." "hasil = [] sementara bagian depan dan belakang: # memilih yang lebih kecil dari depan dan tongkat di # dicatat bahwa list.pop (0) adalah sebuah operasi linear, jadi ini memberikan kuadrat waktu berjalan .. (. result.append front.pop (0) jika [depan 0] <= kembali [0] back.pop lain (0)) # menambahkan result.extend sisa akhir (depan atau belakang) hasil kembali

[sunting] Ruby
def mergesort (daftar) kembali daftar jika
[sunting] Skema

(Define (loe p1 p2);; menerapkan kurang dari atau sama (<= (CDR p1) (CDR p2))) (define (mergesort L) (cond ((= (panjang L) 0) '()) (( = (panjang L) 1) L); daftar elemen 1 adalah diurutkan ((= (panjang L) 2) (jika (<(cdar L) (cdar (CDR L))) L (daftar (mobil (CDR L) ) (car L));; kasus khusus untuk len 2 Daftar)) (lain (mergelist (mergesort (firstn L (/ (panjang L) 2))) (mergesort (lastn L (/ (panjang L) 2))) );; rekursif panggilan mergesort pada kedua bagian))) (define (firstn LN);; pra: N tidak lebih besar dari ukuran L (cond ((= N 0) '()) ((atau (N = 1) ( (cdar primero) (cdar Segundo)) (cons (Segundo mobil) (mergelist primero (CDR Segundo));; kedua kasus utama))))

[sunting] Seed7
Versi tanpa penyimpanan tambahan
const proc: mergeSort (InOut elemType array: arr, di var integer: lo, dalam integer: hi) adalah var integer lokal func: pertengahan adalah 0; elemType var: bantuan elemType.value; var integer: k 0; dimulai jika lo Asli sumber: [1]
Versi dengan penyimpanan tambahan
const proc: mergeSort2 (InOut elemType array: arr, dalam integer: lo, dalam integer: hi, InOut array elemType: nol) adalah var integer lokal func: pertengahan adalah 0; var integer: k 0; var integer: t_lo adalah 0 ; var integer: t_hi adalah 0; mulai jika hai atau arr [t_lo] Asli sumber: [2]
[sunting] Fortran

subroutine Merge (A, NA, B, NB, C, NC) integer, intent (in):: NA, NB, NC! Normal penggunaan: NA NB = NC + integer, niat (di luar):: A (NA)! B lapisan C (NA 1: NC) integer, intent (in):: B (NB) integer, intent (di luar):: C (NC) integer:: I, J, K = 1 saya; J = 1 ; K = 1; melakukan sementara(I <= NA). J dan. <= NB
jika (A (I) <= B (J)) maka C (K) = A (I) I = I 1
lain
C (K) = B (J) J = 1 endif J K = K + 1 enddo melakukan sementara (I <= NA) C (K) = A (I) I = I + 1 K = K + 1 enddo
kembali

akhir subroutine subroutine rekursif menggabungkan MergeSort (A, N, T) integer, intent (in):: integer N, dimensi (N), niat (di luar):: Sebuah integer, dimensi ((N +1) / 2), niat (dari):: T integer:: NA, NB, V

jika (N <2) kembali
jika (N == 2) maka
jika (A (1)> A (2)) maka V = A (1) A ( 1) = A (2) A (2) = V endif
return
endif NA = (N +1) / 2 NB = N-NA panggilan MergeSort (A, NA, T) panggilan MergeSort (A (NA 1), NB , T)

jika (A (NA)> A (NA 1)) maka T (1: NA) = A (1: NA) panggilan Gabung (T, NA, A (NA 1), NB, A, N ) endif
return

akhir program subroutine MergeSort TestMergeSort integer, parameter:: N = 8 integer, dimensi (N):: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /) integer, dimensi (( N +1) / 2):: T panggilan MergeSort (A, N, T) menulis (*, '(A, /, 10I3)')'Diurutkan array:', Sebuah

akhir program TestMergeSort

[sunting] JavaScript

fungsi mergeSort () (
jika(ini.panjang > 1) (
var firstHalf = Math.lantai(ini.panjang / 2);
var secondHalf = ini.panjang - firstHalf;
var arr1 = baru Array(firstHalf);
var arr2 = baru Array(secondHalf);
untuk(var i = 0; i untuk(i firstHalf; = i var i = 0;
var j = 0;
var k = 0;
sementara(arr1.panjang ! = j & & arr2.panjang ! = k ) (
jika(arr1 [j] <= arr2 [k]) (
ini[i] = arr1 [j]; i + +; j + +;) lain (
ini[i] = arr2 k []; i + +; k + +;))
sementara(arr1.panjang )! = j (
ini[i] = arr1 [j]; i + +; j + +;)
sementara(arr2.panjang ! = k) (
ini[i] = arr2 k []; i + +; k + +;)) )
Array.prototipe. mergeSort = mergeSort;

[sunting] Analisis
Dalam pemilahan n item, menggabungkan semacam memiliki rata-rata dan kasus kinerja terburuk O(n log n).Jika waktu berjalan dari merge semacam untuk daftar panjang n adalah T(n), maka pengulangan T(n) = 2T(n/ 2) + n mengikuti definisi dari algoritma (menerapkan algoritma untuk dua daftar setengah ukuran asli daftar, dan tambahkan n langkah-langkah yang diambil untuk menggabungkan dua menghasilkan daftar).Bentuk tertutup berikut dari teorema master.
 

Dalam kasus terburuk, menggabungkan semacam tidak tepat (n ⌈ log n⌉ - 2⌈ log n⌉ + 1) perbandingan, yaitu antara (n log n - n + 1) dan
(n log n - 0,9139 •n + 1) [log basis 2]. Catatan, jumlah kasus terburuk yang diberikan di sini tidak setuju dengan yang diberikan di Knuth's Art of Computer Programming, Vol 3. perbedaan ini karena Knuth menganalisis implementasi varian dari merge semacam yang sedikit sub-optimal.
 

Untuk besar n dan masukan daftar perintah secara acak, seperti yang diharapkan menggabungkan (rata-rata) jumlah pendekatan perbandingan α •n lebih sedikit daripada kasus terburuk, dimana α = -1 + Σ 1 / (2k+1), k = 0 → ∞ , α ≈ 0,2645.
 

Dalam terburuk kasus, menggabungkan semacam tidak sekitar 39% perbandingan kurang dari quicksort tidak dalam rata-rata kasus; menggabungkan semacam selalu membuat perbandingan kurang dari quicksort, kecuali dalam sangat kasus yang jarang terjadi, ketika mereka mengikat, di mana gabungan semacam ituterburuk kasus ditemukan bersamaan dengan quicksort's terbaik kasus. Dalam hal bergerak, menggabungkan kompleksitas kasus semacam terburuk adalah O (n log n)-kerumitan yang sama dengan kasus terbaik quicksort, dan bergabung kasus semacam terbaik membutuhkan waktu sekitar setengah iterasi sebanyak kasus terburuk.
 

Rekursif implementasi merge semacam membuat 2n - 1 metode panggilan dalam kasus terburuk, dibandingkan dengan quicksort's n, sehingga memiliki sekitar dua kali sebagai overhead rekursif sebanyak quicksort.Namun, berulang, non-rekursif, pelaksanaan merger semacam, menghindari panggilan overhead metode, tidak sulit untuk kode. jenis yang paling umum implementasi Merge tidak seperti di tempat, yang berarti memori ukuran input harus dialokasikan untuk diurutkan output yang akan disimpan masuk Sortasi di tempat yang mungkin tetapi membutuhkan pelaksanaan yang sangat rumit dan menyakitkan kinerja.
 

Gabung semacam ini jauh lebih efisien daripada quicksort jika data yang akan diurutkan secara efisien hanya dapat diakses secara berurutan, dan dengan demikian populer di bahasa seperti Lisp, di mana secara berurutan diakses struktur data yang sangat umum. Tidak seperti beberapa (tidak efisien) implementasi dari quicksort, semacam gabungan adalah semacam stabil selama operasi gabungan dilaksanakan dengan benar.
[sunting] Mengoptimalkan menggabungkan semacam
 

Hal ini mungkin tampaknya menjadi kepentingan sejarah saja, tetapi pada komputer modern, lokalitas referensi adalah hal terpenting dalam optimasi perangkat lunak, sebab multi-level hirarki memori digunakan.Dalam hal tertentu, RAM utama dapat dilihat sebagai sebuah tape drive cepat, level 3 cache memori yang sedikit lebih cepat, tingkat 2 cache memori yang lebih cepat lagi, dan seterusnya. Dalam beberapa keadaan, reload cache mungkin memaksakan overhead tidak dapat diterima dan hati-hati dibuat semacam gabungan mungkin mengakibatkan perbaikan yang signifikan dalam menjalankan waktu. Kesempatan ini mungkin berubah jika memori menjadi sangat murah cepat lagi, atau jika arsitektur eksotis seperti MTA Tera menjadi biasa.
 

Merancang gabungan semacam untuk melakukan optimal sering membutuhkan penyesuaian untuk perangkat keras yang tersedia, misalnya. jumlah tape drive, atau ukuran dan kecepatan memori cache tingkat yang relevan.
tanda tangan

Ditulis Oleh : Coretan BoWo ~ Berbagi ilmu

Christian angkouw Terimakasih telah membaca artikel tentang : Mengenal Teknik Marge Sort . Semoga dapat memberikan hal yang positif bagi anda.

:: Coretan BoWo ::

Note :
~ Berikanlah komentar dengan kata-kata yang baik dan sopan.
~ Dilarang mencantumkan link yang berbau negatif.