Mergesort
Teknik pengurutan mergesort lebih cepat dan efisien dibandingkan dengan bubble sort dan insertion sort. Insertion sort dan bubble sort memerlukan waktu O(N2) sedangkan mergesort memerlukan waktu O(N*logN). Sebagai contoh jika N adalah 10.000 data yang diurutkan maka N2 adalah 100.000.000 sementara N*logN hanya 40.000. jika sorting data ini memerlukan waktu 40 detik dengan mergesort maka dengan insertion sort akan memerlukan waktu hampir 28 jam.
Penggabungan 2 array
Inti dari mergesort adalah menggabungkan 2 buah array yang telah terurut dimana array A dan B akan digabungkan menjadi array C dengan data yang telah terurut
Langkah-langkah mergesort
Langkah ke 9 dan ke 10 kosong karena array B telah habis untuk dibandingkan dengan array A. Maka setelahnya sisa array A hanya langsung dipindah ke array C.
Listing mergesort
//merge.cpp
//demonstrates merging two arrays into a third
#include <iostream>
using namespace std;
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void merge( int[], int, int[], int, int[] );
void display(int[], int); //prototypes
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
int main()
{
int arrayA[] = {23, 47, 81, 95}; //source A
int arrayB[] = {7, 14, 39, 55, 62, 74}; //source B
int arrayC[10]; //destination
merge(arrayA, 4, arrayB, 6, arrayC); //merge A+B––>C
display(arrayC, 10); //display result
return 0;
} //end main()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void merge( int arrayA[], int sizeA, //merge A and B into C
int arrayB[], int sizeB,
int arrayC[] )
{
int aDex=0, bDex=0, cDex=0;
while(aDex < sizeA && bDex < sizeB) //neither array empty
if( arrayA[aDex] < arrayB[bDex] )
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] = arrayB[bDex++];
while(aDex < sizeA) //arrayB is empty,
arrayC[cDex++] = arrayA[aDex++]; //but arrayA isn't
while(bDex < sizeB) //arrayA is empty,
arrayC[cDex++] = arrayB[bDex++]; //but arrayB isn't
} //end merge()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––-
void display(int theArray[], int size) //display array
{
for(int j=0; j<size; j++)
cout << theArray[j] << " ";
cout << endl;
}
Output
7 14 23 39 47 55 62 74 81 95
Sorting dengan penggabungan
Ide dari mergesort adalah membagi array menjadi 2 bagian, kemudian tiap bagian diurutkan lalu dilakukan merge atau penggabungan sehingga didapatkan array terurut
Pada gambar diatas array dibagi menjadi masing-masing 2 bagian untuk kemudian urutkan dan digabungkan menjadi 4 bagian kemudian array terurut 4 bagian tersebut digabungkan kembali menjadi array yang terurut. dengan kata lain cara diatas adalah menggunakan pembagian kelipatan 2 yaitu dengan urutan 2,4,8,...dst hingga pada akhirnya array akhir terurut dengan N data.
Program mergesort dengan rekursif
//mergeSort.cpp
//demonstrates recursive merge sort
#include <iostream>
#include <vector>
using namespace std;
////////////////////////////////////////////////////////////////
class DArray
{
private:
vector<double>(theVect); //vector of doubles
int nElems; //number of data items
void recMergeSort(vector<double>, int, int);
void merge(vector<double>, int, int, int);
public:
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
DArray(int max) : nElems(0) //constructor
{
theVect.resize(max); //size vector
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void insert(double value) //put element into array
{
theVect[nElems] = value; //insert it
nElems++; //increment size
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void display() //displays array contents
{
for(int j=0; j<nElems; j++) //for each element,
cout << theVect[j] << " "; //display it
cout << endl;
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void mergeSort() //called by main()
{ //provides workspace
vector<double>(workSpace);
workSpace.resize(nElems);
recMergeSort(workSpace, 0, nElems-1);
}
}; //end class DArray
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void DArray::recMergeSort(vector<double> workSpace,
int lowerBound, int upperBound)
{
if(lowerBound == upperBound) //if range is 1,
return; //no use sorting
else
{ //find midpoint
int mid = (lowerBound+upperBound) / 2;
//sort low half
recMergeSort(workSpace, lowerBound, mid);
//sort high half
recMergeSort(workSpace, mid+1, upperBound);
//merge them
merge(workSpace, lowerBound, mid+1, upperBound);
} //end else
} //end recMergeSort()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void DArray::merge(vector<double> workSpace, int lowPtr,
int highPtr, int upperBound)
{
int j = 0; //workspace index
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1; //# of items
while(lowPtr <= mid && highPtr <= upperBound)
if( theVect[lowPtr] < theVect[highPtr] )
workSpace[j++] = theVect[lowPtr++];
else
workSpace[j++] = theVect[highPtr++];
while(lowPtr <= mid)
workSpace[j++] = theVect[lowPtr++];
while(highPtr <= upperBound)
workSpace[j++] = theVect[highPtr++];
for(j=0; j<n; j++)
theVect[lowerBound+j] = workSpace[j];
} //end merge()
////////////////////////////////////////////////////////////////
int main()
{
const int maxSize = 100; //array size
DArray arr(maxSize); //create "array"
arr.insert(64); //insert items
arr.insert(21);
arr.insert(33);
arr.insert(70);
arr.insert(12);
arr.insert(85);
arr.insert(44);
arr.insert(3);
arr.insert(99);
arr.insert(0);
arr.insert(108);
arr.insert(36);
arr.display(); //display items
arr.mergeSort(); //merge-sort the array
arr.display(); //display items again
return 0;
} //end main()
Output
64 21 33 70 12 85 44 3 99 0 108 36
0 3 12 21 33 36 44 64 70 85 99 108
Jumlah operasi yang dilakukan jika N adalah kelipatan dari 2
Jumlah maksimum dan minimum pembandingan jika digunakan array yang sudah terurut dan array yang tidak terurut dalam mergesort
sumber : Kuliah Logika dan Pemrograman Sistem II
No comments:
Post a Comment