Quick Sort & Merge Sort
printf("Hallo Para Programmer!!");
printf("Disini Saya Akan Membahas Mengenai Algoritma Pengurutan Dalam Bahasa C/C++");
printf("Algoritma Pengurutan Yang Saya Bahas Adalah Quick Sort Dan Merge Sort");
printf("Terus Ikuti Blog Ini Untuk Mendapatkan Artikel Bermanfaat Selanjutnya yah");
printf("Selamat Belajar!!");
1. Algoritma Quick Sort
Metode quick sort dikembangkan oleh C.A.R Hoare.Secara garis besar metode
ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang
mempunyai N elemen. Kita pilih sembarang elemen dari data tersebut, bisanya
elemen pertama, misalnya X. kemudian semua elemen tersebut disusun dengan
menempatkan X pada posisi J sedemikian rupa sehingga elemen ke 1 sampai ke J 1
mempunyai nilai lebih kecil dari X dan elemen J+1sampai ke N mempunyai nilai
lebih besar dari X. Sampai saat ini kita sudah mempunyai dua sub data (kiri dan
kanan). Langkah berikutnya diulang untuk setiap sub data.
2. Algoritma Merge Sort Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya
dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi
algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses
memori acak yang menjaga semua data mu.Hal ini disebabkan algoritma ini
membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan
secara rekursif dan memakai dua tabel.
Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar.
Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali
untuk membentuk tabel yang terurut.Implementasi dasar dari algoritma merge
sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di
bagi dua dan satu untuk menyimpan elemen yang telah terurut.Namun algoritma ini
dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau
memori yang dibutuhkan.
Algoritma Merge umumnya memiliki satu set pointer p0..n yang menunjuk
suatu posisi di dalam satu set daftar L0..n .Pada awalnya mereka menunjuk item yang
pertama pada setiap daftar. Algoritmanya sebagai berikut:
Selama p0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:
- Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing masing.
- Menemukan pointers points untuk item dengan kunci yang paling rendah;
membantu salah satu pointer untuk item yang berikutnya dalam daftar.
CONTOH :
Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan {3,
9, 4, 1, 5, 2} adalah sebagai berikut:
- Larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
- Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4,
9} dan {1, 2, 5}
- Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik
tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1
dalam elemen larik ke dua telah dipindahkan ke larik baru)
- langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam
larik baru yang dibuat sebelumnya.
0 comments:
Posting Komentar