Pengantar Algoritma Merge Sort

Merge sort adalah algoritma pengurutan berdasarkan teknik "membagi dan menaklukkan". Ini adalah salah satu algoritma pengurutan yang paling efisien.

Pada artikel ini, Anda akan mempelajari tentang cara kerja algoritma merge sort, algoritma merge sort, dan kompleksitas ruang dan waktu, serta implementasinya dalam berbagai bahasa pemrograman seperti C++, Python, dan JavaScript.

Bagaimana Cara Kerja Algoritma Merge Sort?

Merge sort bekerja berdasarkan prinsip membagi dan menaklukkan. Merge sort berulang kali memecah array menjadi dua subarray yang sama hingga setiap subarray terdiri dari satu elemen. Akhirnya, semua subarray tersebut digabungkan sedemikian rupa sehingga array yang dihasilkan diurutkan.

Konsep ini dapat dijelaskan lebih efisien dengan bantuan sebuah contoh. Pertimbangkan array yang tidak disortir dengan elemen berikut: {16, 12, 15, 13, 19, 17, 11, 18}.

Di sini, algoritma merge sort membagi array menjadi dua bagian, memanggil dirinya sendiri untuk dua bagian, dan kemudian menggabungkan dua bagian yang diurutkan.

Gabungkan Algoritma Sortir

Berikut adalah algoritma dari merge sort:

MergeSort (arr[], indeks kiri, indeks kanan)
jika indeks kiri >= indeks kanan
kembali
lain
Temukan indeks tengah yang membagi array menjadi dua bagian: 
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Panggil mergeSort() untuk paruh pertama: 
Panggil mergeSort (arr, leftIndex, middleIndex)
Panggil mergeSort() untuk paruh kedua:
Panggil mergeSort (arr, middleIndex+1, rightIndex)
Gabungkan dua bagian yang diurutkan pada langkah 2 dan 3:
Gabungan panggilan (arr, indeks kiri, indeks tengah, indeks kanan)

Terkait: Apa Itu Rekursi dan Bagaimana Cara Menggunakannya?

Kompleksitas Waktu dan Ruang dari Algoritma Merge Sort

Algoritma Merge sort dapat dinyatakan dalam bentuk relasi perulangan berikut:

T(n) = 2T(n/2) + O(n)

Setelah menyelesaikan relasi perulangan ini menggunakan teorema master atau metode pohon perulangan, Anda akan mendapatkan solusinya sebagai O(n logn). Jadi, kompleksitas waktu dari algoritma merge sort adalah O(n log masuk).

Kompleksitas waktu kasus terbaik dari jenis gabungan: O(n log masuk)

Kompleksitas waktu kasus rata-rata dari jenis gabungan: O(n log masuk)

Kompleksitas waktu kasus terburuk dari jenis gabungan: O(n log masuk)

Terkait: Apa itu Notasi Big-O?

Kompleksitas ruang tambahan dari algoritma merge sort adalah Di) sebagai tidak ruang tambahan diperlukan dalam implementasi sortir gabungan.

Implementasi C++ dari Algoritma Merge Sort

Di bawah ini adalah implementasi C++ dari algoritma merge sort:

// implementasi C++ dari of
// menggabungkan algoritma pengurutan
#sertakan 
menggunakan namespace std;
// Fungsi ini menggabungkan dua subarray dari arr[]
// Subarray kiri: arr[leftIndex..middleIndex]
// Subarray kanan: arr[middleIndex+1..rightIndex]
void gabungan (int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Buat array sementara
int L[UkuranSubarraykiri], R[UkuranSubarraykanan];
// Menyalin data ke array sementara L[] dan R[]
untuk (int i = 0; i < leftSubbarraySize; saya++)
L[i] = arr[indeks kiri + i];
untuk (int j = 0; j < rightSubbarraySize; j++)
R[j] = arr[indeks tengah + 1 + j];
// Gabungkan array sementara kembali ke arr[leftIndex..rightIndex]
// Indeks awal subarray kiri
int saya = 0;
// Indeks awal subarray Kanan
int j = 0;
// Indeks awal dari subarray gabungan
int k = indeks kiri;
while (i < leftSubbarraySize && j < rightSubarraySize)
{
jika (L[i] <= R[j])
{
arr[k] = L[i];
saya++;
}
lain
{
arr[k] = R[j];
j++;
}
k++;
}
// Jika ada beberapa elemen yang tersisa di L[]
// Salin ke arr[]
while (i < leftSubbarraySize)
{
arr[k] = L[i];
saya++;
k++;
}
// Jika ada beberapa elemen yang tersisa di R[]
// Salin ke arr[]
sementara (j < rightSubbarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort (int arr[], int leftIndex, int rightIndex)
{
if (indeks kiri >= indeks kanan)
{
kembali;
}
int indeks tengah = indeks kiri + (indeks kanan - indeks kiri)/2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
menggabungkan (arr, indeks kiri, indeks tengah, indeks kanan);
}
// Berfungsi untuk mencetak elemen
// dari array
void printArray (int arr[], int ukuran)
{
untuk (int i = 0; saya < ukuran; saya++)
{
cout << arr[i] << " ";
}
cout<}
// Kode driver
int utama()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int ukuran = ukuran (arr) / ukuran (arr[0]);
cout << "Array tidak disortir:" << endl;
printArray (arr, ukuran);
mergeSort (arr, 0, ukuran - 1);
cout << "Array yang diurutkan:" << endl;
printArray (arr, ukuran);
kembali 0;
}

Keluaran:

Array yang tidak diurutkan:
16 12 15 13 19 17 11 18 
Array yang diurutkan:
11 12 13 15 16 17 18 19

Implementasi JavaScript dari Algoritma Merge Sort

Di bawah ini adalah implementasi JavaScript dari algoritma merge sort:

// implementasi JavaScript dari of
// menggabungkan algoritma pengurutan
// Fungsi ini menggabungkan dua subarray dari arr[]
// Subarray kiri: arr[leftIndex..middleIndex]
// Subarray kanan: arr[middleIndex+1..rightIndex]
fungsi gabungan (arr, indeks kiri, indeks tengah, indeks kanan) {
biarkan leftSubarraySize = middleIndex - leftIndex + 1;
biarkan rightSubarraySize = rightIndex - middleIndex;
// Buat array sementara
var L = Array baru (leftSubbarraySize);
var R = Array baru (rightSubarraySize);
// Menyalin data ke array sementara L[] dan R[]
untuk (misalkan i = 0; sayaL[i] = arr[indeks kiri + i];
}
untuk (misalkan j = 0; jR[j] = arr[indeks tengah + 1 + j];
}
// Gabungkan array sementara kembali ke arr[leftIndex..rightIndex]
// Indeks awal subarray kiri
var saya = 0;
// Indeks awal subarray Kanan
var j = 0;
// Indeks awal dari subarray gabungan
var k = indeks kiri;
while (i < leftSubbarraySize && j < rightSubarraySize)
{
jika (L[i] <= R[j])
{
arr[k] = L[i];
saya++;
}
lain
{
arr[k] = R[j];
j++;
}
k++;
}
// Jika ada beberapa elemen yang tersisa di L[]
// Salin ke arr[]
while (i < leftSubbarraySize)
{
arr[k] = L[i];
saya++;
k++;
}
// Jika ada beberapa elemen yang tersisa di R[]
// Salin ke arr[]
sementara (j < rightSubbarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort (arr, indeks kiri, indeks kanan) {
if (indeks kiri >= indeks kanan) {
kembali
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
menggabungkan (arr, indeks kiri, indeks tengah, indeks kanan);
}
// Berfungsi untuk mencetak elemen
// dari array
fungsi printArray (arr, ukuran) {
untuk (misalkan i = 0; sayadocument.write (arr[i] + " ");
}
dokumen.tulis("
");
}
// Kode pengemudi:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var ukuran = arr.length;
document.write("Array tidak disortir:
");
printArray (arr, ukuran);
mergeSort (arr, 0, ukuran - 1);
document.write("Array terurut:
");
printArray (arr, ukuran);

Keluaran:

Array yang tidak diurutkan:
16 12 15 13 19 17 11 18
Array yang diurutkan:
11 12 13 15 16 17 18 19

Terkait: Pemrograman Dinamis: Contoh, Masalah Umum, dan Solusi

Implementasi Python dari Algoritma Merge Sort

Di bawah ini adalah implementasi Python dari algoritma merge sort:

# Implementasi Python dari
# algoritma pengurutan gabungan
def mergeSort (arr):
jika len (arr) > 1:
# Menemukan indeks tengah array
indeks tengah = len (arr)//2
# Kiri setengah dari array
L = arr[:indeks tengah]
# Separuh kanan array
R = arr[indeks tengah:]
# Mengurutkan paruh pertama array
gabungUrutkan (L)
# Menyortir paruh kedua array
gabungUrutkan (R)
# Indeks awal subarray kiri Left
saya = 0
# Indeks awal subarray Kanan
j = 0
# Indeks awal dari subarray gabungan
k = 0
# Salin data ke array temp L[] dan R[]
sedangkan i < len (L) dan j < len (R):
jika L[i] < R[j]:
arr[k] = L[i]
saya = saya + 1
lain:
arr[k] = R[j]
j = j + 1
k = k + 1
# Memeriksa apakah ada beberapa elemen yang tersisa
sedangkan i < len (L):
arr[k] = L[i]
saya = saya + 1
k = k + 1
sedangkan j < len (R):
arr[k] = R[j]
j = j + 1
k = k + 1
# Berfungsi untuk mencetak elemen
# dari array
def printArray (arr, ukuran):
untuk saya dalam kisaran (ukuran):
cetak (arr[i], akhir=" ")
mencetak()
# Kode pengemudi
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
ukuran = len (arr)
print("Array tidak disortir:")
printArray (arr, ukuran)
mergeSort (arr)
print("Array terurut :")
printArray (arr, ukuran)

Keluaran:

Array yang tidak diurutkan:
16 12 15 13 19 17 11 18
Array yang diurutkan:
11 12 13 15 16 17 18 19

Memahami Algoritma Penyortiran Lainnya

Sorting adalah salah satu algoritma yang paling banyak digunakan dalam pemrograman. Anda dapat mengurutkan elemen dalam bahasa pemrograman yang berbeda menggunakan berbagai algoritme pengurutan seperti pengurutan cepat, pengurutan gelembung, pengurutan gabungan, pengurutan penyisipan, dll.

Bubble sort adalah pilihan terbaik jika Anda ingin belajar tentang algoritma pengurutan yang paling sederhana.

Pengantar Algoritma Bubble Sort

Algoritma Bubble Sort: pengenalan yang sangat baik untuk mengurutkan array.

Baca Selanjutnya

Tentang Penulis