IMPROVING PERFORMANCE OF RANDOMIZED SIGNATURESORT USING HASHING AND BITWISE OPERATORS

Journal of Global Research in Computer Sciences

article

Tamana Pathak¹  Deepak Garg¹ 

[1] Department of computer Science and Engineering, Thapar University

关键词: Randomized algorithms;    Sorting;    Integer Sorting;    Linear Complexity;   

来源: Research & Reviews

【 摘 要 】

Research done in the area of integer sorting has considerably improved the lower bound and achieved with comparison sorting i.e. to [1] for a deterministic algorithms or to for a radix sort algorithm in space that depends only on the number of input integers. Andersson et al. [2] presented signature sort in the expected linear time and space which gives very bad performance than traditional quick sort. It is well known that integers in the range [1, c] can be sorted in time using radix sorting. Integers in any range [1, ] can be sorted in time [1]. However, these algorithms use words of extra memory. We present a simple and stable variant of signature sort for integer sorting, which works in time and uses only words of extra memory. In this we are trying to improve the performance of the signature sort by implementing differently and comparing its performance against traditional sorting algorithms and to see the effect of register size on the algorithm.

【 授权许可】

Unknown