CFP last date
22 April 2024
Reseach Article

Space Optimization of Counting Sort

Published on April 2016 by Aishwarya Kaul
International Conference on ICT for Healthcare
Foundation of Computer Science USA
ICTHC2015 - Number 1
April 2016
Authors: Aishwarya Kaul
4d9a31d7-fc5f-49d5-9098-4abe98b52b9a

Aishwarya Kaul . Space Optimization of Counting Sort. International Conference on ICT for Healthcare. ICTHC2015, 1 (April 2016), 7-11.

@article{
author = { Aishwarya Kaul },
title = { Space Optimization of Counting Sort },
journal = { International Conference on ICT for Healthcare },
issue_date = { April 2016 },
volume = { ICTHC2015 },
number = { 1 },
month = { April },
year = { 2016 },
issn = 0975-8887,
pages = { 7-11 },
numpages = 5,
url = { /proceedings/icthc2015/number1/24652-8250/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference on ICT for Healthcare
%A Aishwarya Kaul
%T Space Optimization of Counting Sort
%J International Conference on ICT for Healthcare
%@ 0975-8887
%V ICTHC2015
%N 1
%P 7-11
%D 2016
%I International Journal of Computer Applications
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
  1. Comparison of Bucket Sort and RADIX Sort, Panu Horsmalahti panu. horsmalahti@tut. fi, June 18, 2012
  2. Energy consumption analysis of parallel sorting algorithms running on multicore systems, Zecena et al
  3. Integer sorting algorithms for coarse-grained parallel machines, AlSabti, K. , Ranka, S.
  4. http://video. mit. edu/watch/introduction-to-algorithms-lecture-7-counting-sort-radix-sort-lower-bounds-for-sorting-14155/
  5. 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
  6. T. H. Cormen, C. E. Leiserson, R. L Rivest, and C. Stein. Introduction to Algorithms". MIT Press, 3nd edition edition
  7. Curtis R. Cook and Do Jin Kim. Best sorting algorithm for nearly sorted lists". Commun. ACM, 23(11):620-624, November 1980
  8. 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
  9. 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
  10. The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions, Robert Armstrong, Hensgen, Debra, Taylor Kidd
  11. An optimal parallel algorithm for integer sorting, Reif, J. H. , Foundations of Computer Science, 1985. , 26th Annual Symposium
  12. 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)
  13. Parallel Algorithm for Integer Sorting with Multicore Processors, by S. Stoichev and S. Marinova
  14. 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
  15. Analysis of Algorithms I: Counting and Radix Sort, Xi Chen, Columbia University
Index Terms

Computer Science
Information Sciences

Keywords

Algorithms Counting Sort Design Optimization Performance Sorting