An approach to parallel sorting using ternary search
Автор: Monica Maurya, Alka Singh
Журнал: International Journal of Modern Education and Computer Science @ijmecs
Статья в выпуске: 4 vol.10, 2018 года.
Бесплатный доступ
This paper describe a parallel sorting algorithm which is the combination of counting sort and ternary search. The proposed algorithm is based on split and concurrent selection strategy. First of all the data sequence is distributed among the different processors and are sorted in parallel using counting sort. Then it applies ternary search to find the index position of all elements globally to find the correct position of each elements in data sequence. This paper analyses the computational complexity of proposed parallel sorting algorithm and compares it with some of existing algorithms. The results of proposed algorithms shows that it is better than existing parallel sorting algorithm like parallel merge sort and binary search based sorting algorithm.
Counting sort, Ternary search, Parallel Merge sort, Binary search, Bitonic Sort
Короткий адрес: https://sciup.org/15016753
IDR: 15016753 | DOI: 10.5815/ijmecs.2018.04.05
Список литературы An approach to parallel sorting using ternary search
- Olabiyisi S.O, Adetunji A. B, Oyeyinka F. I. “An Evaluation of Factors Affecting the Efficiency of Some Sorting Techniques”, IJMECS, vol.5,no.2,pp 25-33,2013.DOI:10.5815/ijmecs.2013.02.04.
- Sherin W. Hijazi, Mohammad Qatawneh ‘Study of Prformance Evaluationof Binary Search on Merge Sorted Array Using Different Strategies, IJMECS, vol. 9, no. 12, pp.1-8,2017. DOI:10.5815/ijmecs.2017.12.01.
- Cormen, Thomas H, Leiserson, Charles E., Rivest,Ronald L.(1990). ʻʻIntroduction to Algorithms(1st Ed.) ʼʼ. MIT Press and McGraw-Hill. ISBN 0-262-0141-8.
- Manpreet Singh Bajwa, Arun Prakash Agarwal, Sumanti Manhana.ʻʻTernary Search Algorithm: Improvement of Binary Searchʼʼ, 2nd International Conference on Computing for Sustainable Global Development(INDIAcom), (2015).
- G. Koch, ʻʻMulti-core Introductionʼʼ, Intel Developer Zone, http://software.intel. com/ensus/articles/ multi-core introduction, (2013).
- Kalim Qureshi and Haroon Rashid,ʻʻA Practical Performance comparison of Parallel Matrix Multiplication Algorithms on network of workstations.ʼʼ,I Transaction Japan, Vl. 125, N 3, 2005.
- A. Sohnans and Y. Kodama,ʻʻLoad Balanced Radix sortʼʼ In Proceedings of the 12th International Conference on Supercomputing,(1998), pp.305-312.
- D. R. Helman, D. D. Bader and J. Jaja.ʻʻA Randomized Parallel Sort Algorithm with an Expermental studyʼʼ, Journal of Parallel an Distribute Computing vol.53(1998), pp.1-23.
- X.-j. Qian, J. –b. Xu ʻʻOptimization an Implementation of Sorting Algorithm based Multi-Core an Multi-Thread ʼʼ, IEEE 3rd International Conference on Communciation Software and Networks,(2011),pp.29-32.
- S Nadathur, M. Harris and M. Garland,ʻʻ Designing Efficient Sorting Algorithms for many Core GPU’sʼʼ,IEEE International Symposism on Parallel an Distributed Processing ,(2009),pp. 23-29.
- E. Sintroon and U. Assarsson,ʻʻFast Parallel GPU Sorting using a Hybrid Algorithm.ʼʼ Journal of Parallel and Distributed Computing,vol.66.(2008),pp.1381-1388.
- G.S. Almasi an A. Gottieb,ʻʻHighly Parallel Computingʼʼ, Benjamin Cummings Publishers, CA,USA,(1989).
- E. Masato, ʻʻ Parallelizing Fundamental Algorithms such as Sorting on Multi-core Processors for EDA Acceleration ʼʼ,Proceedings of the 2009 Asia and South Pacific Design Automation Conference.(2009),pp.230-233.
- Sweta Kumari and Dhirendra Pratap Singh “A Parallel Selection Sorting Algorithm on GPUs Using Binary Search”, IEEE International Conference on Advances in Engineering and Technology and Research(ICAETR-2014).
