Space Optimization of Counting Sort
Aishwarya Kaul. Article: Space Optimization of Counting Sort. IJCA Proceedings on International Conference on ICT for Healthcare ICTHC 2015(1):7-11, April 2016. Full text available. BibTeX
@article{key:article,
author = {Aishwarya Kaul},
title = {Article: Space Optimization of Counting Sort},
journal = {IJCA Proceedings on International Conference on ICT for Healthcare},
year = {2016},
volume = {ICTHC 2015},
number = {1},
pages = {7-11},
month = {April},
note = {Full text available}
}
Abstract
Optimization of sorting algorithms is an ongoing research and delivers faster and less space consuming algorithms. The Counting sort algorithm is an integer sorting algorithm and is a very simple and effective way to sort numbers based on their key value. It uses three arrays for computation but in a large input set it can consume a significant amount of memory. This paper puts forward a method to reduce the amount of space required to perform the computation. It reduces the number of arrays or memory required for computation by using just two arrays instead of three, i. e. the input and the count array, removing the need of the third output array.
References
- Comparison of Bucket Sort and RADIX Sort, Panu Horsmalahti panu. horsmalahti@tut. fi, June 18, 2012
- Energy consumption analysis of parallel sorting algorithms running on multicore systems, Zecena et al
- Integer sorting algorithms for coarse-grained parallel machines, AlSabti, K. , Ranka, S.
- http://video. mit. edu/watch/introduction-to-algorithms-lecture-7-counting-sort-radix-sort-lower-bounds-for-sorting-14155/
- Counting and Occurrence Sort for GPUs using an Embedded Language, Josef Svenningsson, Bo Joel Svensson, Mary Sheeran, Dept of Computer Science and Engineering Chalmers University of Technology, {josefs, joels, ms}@chalmers. se
- T. H. Cormen, C. E. Leiserson, R. L Rivest, and C. Stein. Introduction to Algorithms". MIT Press, 3nd edition edition
- Curtis R. Cook and Do Jin Kim. Best sorting algorithm for nearly sorted lists". Commun. ACM, 23(11):620-624, November 1980
- Integer sorting in O(1) time on an n*n reconfigurable mesh, Olariu, S. , Schwing, J. L. , Zhang, J. , Computers and Communications, 1992. Conference Proceedings, Eleventh Annual International Phoenix Conference
- Design and implementation of an efficient integer count sort in CUDA GPUs, Vasileios Kolonias, Artemios G Voyiatzis, George Goulas, Efthymios Housos, Concurrency and Computation: Practice and Experience
- The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions, Robert Armstrong, Hensgen, Debra, Taylor Kidd
- An optimal parallel algorithm for integer sorting, Reif, J. H. , Foundations of Computer Science, 1985. , 26th Annual Symposium
- Paper on "Implementation of the technique of Space minimization for Counting Sort algorithm" by Sanjeev Kumar Sharma ,Professor and Dean, JP Institute of Engineering & Technology, Meerut, dean. ar@jpiet. com and Prem Sagar Sharma Research Scholar, Premsagar1987@rediffmaomil. c at Conference on Advances in Communication and Control Systems 2013 (CAC2S 2013)
- Parallel Algorithm for Integer Sorting with Multicore Processors, by S. Stoichev and S. Marinova
- Accelerating a Particle-In-Cell Simulation using a Hybrid Counting Sort, K. J. Bowers, Electrical Engineering and Computer Science Department University of California at Berkeley
- Analysis of Algorithms I: Counting and Radix Sort, Xi Chen, Columbia University