CFP last date
22 April 2024
Reseach Article

Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms

by Ishwari Singh Rajput, Bhawnesh Kumar, Tinku Singh
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 57 - Number 9
Year of Publication: 2012
Authors: Ishwari Singh Rajput, Bhawnesh Kumar, Tinku Singh
10.5120/9142-3363

Ishwari Singh Rajput, Bhawnesh Kumar, Tinku Singh . Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms. International Journal of Computer Applications. 57, 9 ( November 2012), 14-22. DOI=10.5120/9142-3363

@article{ 10.5120/9142-3363,
author = { Ishwari Singh Rajput, Bhawnesh Kumar, Tinku Singh },
title = { Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { November 2012 },
volume = { 57 },
number = { 9 },
month = { November },
year = { 2012 },
issn = { 0975-8887 },
pages = { 14-22 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume57/number9/9142-3363/ },
doi = { 10.5120/9142-3363 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:01:20.608665+05:30
%A Ishwari Singh Rajput
%A Bhawnesh Kumar
%A Tinku Singh
%T Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 57
%N 9
%P 14-22
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Sorting is among the first of algorithm, than any computer science student encounters during college and it is considered as a simple and well studied problem. With the advancement in parallel processing many parallel sorting algorithms have been investigated. These algorithms are designed for a variety of parallel computer architectures. In this paper, a comparative analysis of performance of three different types of sorting algorithms viz. sequential quick sort, parallel quick sort and hyperquicksort is presented. Quick sort is a divide-and-conquer algorithm that sorts a sequence by recursively dividing it into smaller subsequences, and has ?(nlogn) complexity for n data values. The comparative analysis is based on comparing average sorting times and speedup achieved in parallel sorting over sequential quick sort and comparing number of comparisons. The time complexity for each sorting algorithm will also be mentioned and analyzed.

References
  1. Madhavi Desai, Viral Kapadiya, Performance Study of Efficient Quick Sort and Other Sorting Algorithms for Repeated Data, National Conference on Recent Trends in Engineering & Technology, 13-14 May 2011.
  2. D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second ed. Boston, MA: Addison-Wesley, 1998.
  3. Grama A. , A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, Addison Wesley, 2003.
  4. M. J. Quinn, Parallel Programming in C with MPI and OpenMP, Tata McGraw Hill Publications, 2003, p. 338.
  5. C. A. R. Hoare, Quick sort, Computer Journal, Vol. 5, 1, 10-15 (1962).
  6. S. S. Skiena, The Algorithm Design Manual, Second Edition, Springer, 2008, p. 129.
  7. Abdulrahman Hamed Almutairi & Abdulrahman Helal Alruwaili, Improving of Quick sort Algorithm performance by Sequential Thread or Parallel Algorithms, Global Journal of Computer Science and Technology Hardware & Computation Volume 12 Issue 10 Version 1. 0, 2012.
  8. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to algorithms, MIT Press 1990.
  9. Akl, S. G. , Parallel Sorting Algorithms, Academic Press, Orlando, Florida, 1985.
  10. Borovska P. , Synthesis and Analysis of Parallel Algorithms, Technical University of Sofia, 2008, ISBN: 978-954-438-764-4.
  11. Quinn, M. J. , Parallel Computing Theory and Practice, Tata Mcgraw Hill Publications (2002), p. 277.
  12. Akl, S. G. , Design and Analysis of Parallel Algorithms, Academic Press, Orlando, Florida, (1985).
  13. P. Heidelberger, A. Norton, and J. T. Robinson. Parallel quicksort using Fetch-and-Add. IEEE Transactions on Computers, 39(1):133–137, January 1990.
  14. Evans, D. J. and Yousif, N. Y. , The Parallel Neighbor Sort and Two-way Merge Algorithm, Parallel Computing 3, (1986), 85-90.
Index Terms

Computer Science
Information Sciences

Keywords

Algorithm quick sort parallel sorting algorithms parallel quick sort hyperquicksort performance analysis