원문정보
초록
영어
Many sorting algorithms have been proposed and implemented in previous years. These algorithms are usually judged by their performance in term of algorithm growth rate according to the input size. Efficient sorting algorithm implementation is important for optimizing the use of other algorithms such as searching algorithms, load balancing algorithms, etc. In this paper, parallel Quicksort, parallel Merge sort, and parallel Merge-Quicksort algorithms are evaluated and compared in terms of the running time, speedup, and parallel efficiency. These sorting algorithms are implemented using Message Passing Interface (MPI) library, and results have been conducted using IMAN1 supercomputer. Results show that the run time of parallel Quicksort algorithm outperforms both Merge sort and Merge-Quicksort algorithms. Moreover, on large number of processors, parallel Quicksort achieves the best parallel efficiency of up to 88%, while Merge sort and Merge-Quicksort algorithms achieve up to 49% and 52% parallel efficiency, respectively.
목차
1. Introduction
2. Related Works
3. An Overview of Sequential and Parallel Quicksort
3.1. Sequential Quicksort
3.2. Parallel Quicksort
4. An Overview of Sequential and Parallel Merge Sort
4.1. Sequential Merge Sort
4.2. Parallel Merge Sort
5. An Overview of Parallel Merge-Quicksort
6. Performance Evaluation and Results
6.1. Run Time Evaluation
6.2. Speedup Evaluation
6.3. Parallel Efficiency Evaluation
7. Conclusion
References