Contoh Program Pengurutan Dengan Penggabungan atau Merge Sort

Contoh Program Pengurutan Dengan Penggabungan atau  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:

 rumus 300x128 Contoh Program Pengurutan Dengan Penggabungan atau  Merge SortSehingga, algoritma merge sort memiliki kompleksitas algoritma O(n log n). Algoritma merge 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.

Contoh Program Pengurutan Dengan Penggabungan atau  Merge Sort


Read previous post:
Tips Menjadi Istri Yang Baik

Tips Menjadi Istri Yang Baik - Untuk menjadi istri yang baik merupakan idaman bagi setiap...

Close