ALGORITMA MERGE SORT

Algoritma Merge Sort

Penjelasan Algoritma merge sort membagi (split) tabel menjadi dua  tabel sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. contoh dari bahasa C ini tidak jauh berbeda dengan program delphi.

Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah dibagi dua dan satu untuk menyimpan elemen yang telah teurut. Namun

algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Di bawah ini adalah algoritma untuk merge sort yang dilakukan pada dua tabel dalam notasi C.

Contoh Program Pengurutan Dengan Penggabungan atau  Merge Sort :

void mergeSort (int *T, int *temp, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S T terturut menaik*/
/* Proses : melakukan pengurutan*/
/*         dengan melakukan metode sort*/
{
m_sort (T, temp, 0, Nmax -1);
}
void m_short (int *T, int *temp, int *left, int *right)
{
int mid;
if (*right > *left)
{
mid = (*right + *left) / 2;
m_sort (T, temp, left, mid);
m_sort (T, temp, mid+1, right);
merge (T, temp, left, mid+1, right);
}
}
void merge(int *T, int * temp, int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end + mid-1;
tmp_pos = left;
num_elements = right – left + 1;
while ((left <= left_end) && (mid <= right))
{
if (*T[left] <= *T[mid])
{
*temp[tmp_pos] = *T[left];
tmp_pos = tmp_pos +1;
left = left +1;
}
else
{
*temp [tmp_pos] = *T [mid];
tmp_pos = tmp_pos + 1;
mid = mid +1;
}
}
while (left <= left_end);
{
*temp[tmp_pos] = *T[left];
left = left +1;
tmp_pos = tmp_pos +1;
}
while (mid <= right)
{
*temp [tmp_pos] = *T [mid];
mid = mid +1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
*T[right] = *temp[right];
right = right -1;
}
}

 

Karena algoritma merge sort adalah algoritma yang dijalankan secara rekursif maka T(n) dari algoritma ini adalah:

 

Sehingga, algoritma merge sort memiliki kompleksitas algoritma O(n log n). Algoritmamerge sort ini sebenernya lebih cepat dibandingkan heap sort untuk tabel yang lebih besar. Namun, algoritma ini membutuhkan setidakny ruang atau emori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel. Hal ini menyebabkan algoritma ini kurang banyak dipakai.

Mungkin itu sedikit yang saya ketahui dari Merge Sort, sekian dan terima kasih..dan Saya sangat berterimakasih jika anda bersedia memberikan kritik, saran maupun komentar atas kekurangan, error, broken links dan lainnya, masukan dari anda sangat membantu untuk perbaikan tutorial maupun blog ini.

SUMBER : http://kandiwa.blogspot.com/2012/06/algoritma-merge-sort.html