Parallel Two-Dimensional Quicksort Algorithm (PTSA)
Abstract
In this research, a Parallel Two-Dimensional Sorting Algorithm (PTSA) is presented that has better performance than the classical Quicksort, to sort a data vector of size n = r (rows) × c(columns). PTSA algorithm divides the input vector into n/r sub-vectors, which represents tow-dimensional vector of Slave Processor Elements (VPE ), the maximum number of VPE for parallel sorting is equal to r×c, VPE just the read,and write operations. The number of Master Processors (MP) which do the sort operation is equal to c, The time needed for PTSA algorithm is reduced by θ (n/r log n/r) with respect to the time needed by Quicksort θ (n log n) to sort the same vector. Simulation results show that the efficiency of sorting using PTSA algorithm is increased and the complexity is reduced significantly compared with classical Quicksort.
DOI: https://doi.org/10.3844/jcssp.2008.66.71
Copyright: © 2008 Hamed Al Rjoub, Ahmad Odat and Abdullah Audat. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,066 Views
- 2,689 Downloads
- 1 Citations
Download
Keywords
- Data mining
- accelerate
- sorting rows
- sorting columns
- proccessors
- iterations