IMPLEMENTASI PEMROGRAMAN PARALEL DALAM HIBRIDISASI ALGORITMA SHELL SORT DAN QUICK SORT
Daftar Isi:
- Adanya kelebihan dan kekurangan pada algoritma pengurutan data (sorting) pada pengurutan data yang kecil dan besar membuat pengurutan data menjadi tidak efisien, terlebih lagi karena pada dasarnya suatu algoritma dibangun menggunakan komputasi serial yang membutuhkan waktu pemrosesan yang lama. Agar menghasilkan algoritma pengurutan data (sorting) yang cepat dalam pengurutan data sedikit maupun data banyak, maka dilakukan perbaikan, dengan cara mengkombinasikan (hybrid) algoritma satu dengan yang lain. Pada penelitian ini, algoritma Shell sort dengan Quick sort dikombinasikan (hybrid) dan diimplementasikan ke dalam pemrograman paralel berbasis Message Passing Interface (MPI) menggunakan dua komputer. Dalam penelitian ini juga telah dilakukan analisis pendahuluan, rancang bangun jaringan fisik, rancang bangun kode program paralel dalam bahasa C, pengambilan data waktu eksekusi, pengolahan data waktu eksekusi, analisis kecepatan pemrosesan (speed up) dan efisiensi penggunaan dua komputer. Dari pengujian pada 5-5000 sampel data acak, dapat disimpulkan bahwa speed up program hybrid algoritma Shell sort dan Quick sort cenderung meningkat dan efisiensi masih dalam batas 50%-100%, hanya saja mengalami penurunan kecepatan pada 50-100 data, dengan nilai speed up 0,671201-0,784806 dan dengan nilai efisiensi terendah 34%-39%. Selain itu, program hybrid algoritma Shell sort dan Quick sort mengalami percepatan superlinier pada pengurutan 1000 data acak dengan nilai speed up 2,4909998 dan dengan nilai efisiensi tertinggi mencapai 125%. Kata kunci : algoritma, bahasa C, sorting, Shell sort, Quick sort, hybrid, message passing interface, speed up, efisiensi.