Algoritma Divide and Conquer

Algoritma Divide and Conquer adalah algoritma pemecahan masalah dengan cara membagi masalah kedalam bagian-bagian kecil, kemudian menyelesaikan masalah tersebut dari bagian yang paling rendah / bawah. Contoh kasus yang akan dibahas kali ini adalah teknik pengurutan data menggunakan Merge Sort.

Pada contoh kasus ini akan dibandingkan 2 cara pengurutan bilangan acak, yaitu dengan menggunakan teknik Bubble Sort dan teknik Merge Sort. Algoritma Divide and Conquer akan digunakan dalam teknik Merge Sort.

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data adalah sebagai berikut

Dim randomNumber As New Random
Dim data(19) As Integer
Dim s As String = ""
For i As Integer = 0 To 19
	data(i) = randomNumber.Next(0, 99)
	s = s & data(i) & IIf(i <> 19, ", ", "")
Next

A. Teknik Bubble Sort
Bubble sort adalah teknik pengurutan dengan cara membandingkan semua kemungkinan data,
Teknik pengurutan ini adalah pengurutan yang paling mudah, namun paling tidak efisien

Dim bubbleSort(19) As Integer
For i As Integer = 0 To 19
	bubbleSort(i) = data(i)
Next

Dim totBubbleSort As Integer = 0
Dim tmpdata As Integer = 0
For i As Integer = 0 To 19
	For j As Integer = 0 To 19
		If i <> j And bubbleSort(i) > bubbleSort(j) Then
			tmpdata = bubbleSort(i)
			bubbleSort(i) = bubbleSort(j)
			bubbleSort(j) = tmpdata
		End If
		totBubbleSort += 1
	Next
	totBubbleSort += 1
Next

B. Teknik Merge Sort
Merge sort adalah teknik pengurutan yang lebih efisien
Dalam kasus ini, teknik ini akan dilakukan dengan menggunakan algoritma Divide and Conquer
Pengurutan akan dilakukan di dalam fungsi MergeSort

Dim dataMergeSort(19) As Integer
For i As Integer = 0 To 19
	dataMergeSort(i) = data(i)
Next

MergeSort(dataMergeSort)

Langkah-langkah penggunaan algoritma ini adalah

:
1. Tentukan konstanta pembagian data
Seberapa banyak data akan dibagi pada setiap prosesnya
Diasumsikan dalam kasus ini, data akan dibagi menjadi 2 bagian, yaitu bagian kiri dan kanan
Jadi pada setiap perhitungan nya hanya ada 2 proses, yaitu pengurutan data untuk data bagian kiri dan kanan

Dim mid As Integer = (UBound(data) + 1) / 2

2. Lakukan proses pembagian data pada bagian kiri jika jumlah data nya masih lebih dari 2

Dim mergeSortLeft() As Integer
ReDim mergeSortLeft(mid - 1)
For i As Integer = 0 To mid - 1
	mergeSortLeft(i) = data(i)
Next
totMergeSort += 1
MergeSort(mergeSortLeft)

3. Lakukan proses pembagian data pada bagian kanan jika jumlah data nya masih lebih dari 2

Dim mergeSortRight() As Integer
ReDim mergeSortRight(UBound(data) - mid)
For i As Integer = mid To UBound(data)
	mergeSortRight(i - mid) = data(i)
Next
totMergeSort += 1
MergeSort(mergeSortRight)

4. Jika jumlah datanya 2, maka lakukan proses pengurutan data

If UBound(data) = 1 Then
	Dim tmpdata As Integer = 0
	If data(0) < data(1) Then
		tmpdata = data(0)
		data(0) = data(1)
		data(1) = tmpdata

		totMergeSort += 1
	End If
	Return
End If

5. Setelah data bagian kiri dan kanan sudah diurutkan, maka lakukan pengurutan data secara gabungan

Dim iCount As Integer = 0
Do While UBound(mergeSortLeft) >= 0 Or UBound(mergeSortRight) >= 0
	If UBound(mergeSortLeft) >= 0 And UBound(mergeSortRight) >= 0 Then
		If mergeSortLeft(UBound(mergeSortLeft)) < mergeSortRight(UBound(mergeSortRight)) Then
			data(UBound(data) - iCount) = mergeSortLeft(UBound(mergeSortLeft))
			ReDim Preserve mergeSortLeft(UBound(mergeSortLeft) - 1)
		Else
			data(UBound(data) - iCount) = mergeSortRight(UBound(mergeSortRight))
			ReDim Preserve mergeSortRight(UBound(mergeSortRight) - 1)
		End If
		iCount += 1
		totMergeSort += 1

	ElseIf UBound(mergeSortLeft) >= 0 Then
		data(UBound(data) - iCount) = mergeSortLeft(UBound(mergeSortLeft))
		ReDim Preserve mergeSortLeft(UBound(mergeSortLeft) - 1)
		iCount += 1
		totMergeSort += 1

	ElseIf UBound(mergeSortRight) >= 0 Then
		data(UBound(data) - iCount) = mergeSortRight(UBound(mergeSortRight))
		ReDim Preserve mergeSortRight(UBound(mergeSortRight) - 1)
		iCount += 1
		totMergeSort += 1
	End If
Loop

Hasil akhir adalah: (klik untuk perbesar gambar)

Bisa dilihat bahwa teknik pengurutan data dengan menggunakan Merge Sort lebih cepat daripada teknik Bubble Sort.

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.