A parallel partition for enhanced parallel QuickSort
| Autor: | Rhys S. Francis, L. J. H. Pannan |
|---|---|
| Rok vydání: | 1992 |
| Předmět: |
Sorting algorithm
Cost efficiency Computer Networks and Communications Computer science Parallel algorithm Partition problem Sorting Multiprocessing Parallel computing Computer Graphics and Computer-Aided Design Partition (database) Theoretical Computer Science MIMD Shared memory Artificial Intelligence Hardware and Architecture Partition (number theory) Algorithm Software Quicksort |
| Zdroj: | Parallel Computing. 18:543-550 |
| ISSN: | 0167-8191 |
| DOI: | 10.1016/0167-8191(92)90089-p |
| Popis: | QuickSort is a favoured sequential internal sorting algorithm due to its fast average running time and its small memory requirements. Previous investigations into its parallel execution have failed to address the O(n) running time of the partition step with consequent performance limitations. This paper presents an effective parallel partitioning algorithm for the shared memory multiprocessor model. The parallel partition algorithm involves slicing the original data set into several independent subsets. Concurrent partitioning of the subsets is followed by a sequential combination process to finalize the partition. The cost of this sequential combination process is very much less than the cost of the original sequential partition, leading to enhanced algorithmic performance of parallel QuickSort. The technique used to successfully parallelize an operation which on the surface appears to be inherently sequential is also of interest. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|