Unisort: an Algorithm to Sort Uniformly Distributed Numbers in O(n) Time


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


In recent years, computer science specialists are faced with the challenge of processing massive amounts of data. To overcome this barrier, researchers have developed new techniques to process data in efficient ways. This paper aims to present an algorithm for sorting uniformly distributed numbers, called Unisort. Given a uniformly distributed array of numbers, the algorithm places the numbers into bins to obtain sorted sub-arrays. It then merges the sorted sub-arrays to obtain the final sorted array. This work demonstrates that if numbers are uniformly distributed, the algorithm is able to sort them in O(n) time. Furthermore, the algorithm can be generalized to numbers produced by any known distribution. The only requirement is to know the distribution a priori. However, in the worst case scenario, when the distribution is not known, the numbers may fall in the same bin. For the worst case, the algorithm becomes similar to merge sort. Experiments conducted to assess the performance level of the algorithm, in terms of time efficiency, show that it is faster than quicksort, heapsort and Bucket sort. The algorithm has broad applications in information technology, since almost every information system organizes data by sorting it


Copyright © 2013 Praise Worthy Prize - All rights reserved.

Keywords


Sorting Algorithm; Uniformly Distributed Numbers; Fast Sorting Algorithm; Efficient Sort; Fast Sort; Uniform Distribution; Distribution Sort; Sorting by Address Calculation

Full Text:

PDF


References


M. Hilbert, P. Lopez, The World’s Technological Capacity To Store, Communicate and Compute Information, Science, vol. 332 n. 6025, April 2011, pp. 60 – 65.
http://dx.doi.org/10.1126/science.1200970

C.A.R. Hoare, Quicksort, The Computer Journal, vol. 5 n. 1, 1962, pp. 10 – 16.
http://dx.doi.org/10.1093/comjnl/5.1.10

R. Sedgewick, Algorithms In C: Fundamentals, Data Structures, Sorting, Searching (Pearson Education, September 1998).

J.W.J. Williams, Algorithm 232 Heapsort, Communications of the ACM (CACM), vol. 7 n. 6, June 1964, pp. 347 – 348.

E. Corwin, A. Logar, Sorting in linear time – variantion on the bucket sort, Journal of Computer Science in Colleges, vol. 20 n. 1, October 2004, pp. 197 – 202.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Second Edition, 8.4 (MIT Press and McGraw-Hill, 2001, 174-177).

Vasilev, N.B., Bosakova-Ardenska, A.D., Algorithms for sorting by left-in version stable, (2012) International Review on Computers and Software (IRECOS), 7 (2), pp. 642-650.

P.E. Black, Histogram sort, NIST Dictionary of Algorithms and Data Structures, (November 2009).

E.J. Isaac, R.C. Singleton, Sorting by Address Calculation, Journal of the ACM (JACM), vol. 3 n. 3, July 1956, pp. 169 – 174.
http://dx.doi.org/10.1145/320831.320834

C.J. Huang, C.T. Guan, Y.T. Chuang, A key-address mapping sort algorithm, In Proceedings of the 5th WSEAS International Conference on APPLIED COMPUTER SCIENCE ~ACOS 2006~, 2006, pp. 352 – 357.

D. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition (Addison-Wesley, 1998).


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize