Paper Info
Title
A VLSI partition algorithm
Abstract
A VLSI sorter of sizeO(n) can sortn elements in linear time when the input and output time are taken into account. If the input contains more thann elements, some prepocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner isO(logk) for a data file of sizekn wheren is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must goO(k) times through the partitioner like in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.
Year
DOI
Venue
1988
10.1007/BF01934087
BIT
Keywords
Field
DocType
vlsi partition algorithm,linear time,priority queue
Partition problem,Shift register,Computer science,Queue,Parallel computing,Algorithm,Input/output,Quicksort,Priority queue,Time complexity,Very-large-scale integration
Journal
Volume
Issue
ISSN
28
2
0006-3835
Citations 
PageRank 
References 
0
0.34
5
Authors
1
Name
Order
Citations
PageRank
Shou-hsuan Stephen Huang117459.88