Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7479
 Title: Sorting and Searching Using Controlled Density Arrays Authors: Melville, Robert C.Gries, David Keywords: computer sciencetechnical report Issue Date: Dec-1978 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR78-362 Abstract: Algorithms like insertion sort run slowly because of costly shifting of array elements when a value is inserted or deleted. The amount of shifting, however, can be reduced by leaving gaps - unused array locations into which new values can be inserted - at regular intervals in the array. The proper arrangement of gaps is maintained by periodic adjustment. We demonstrate this technique with a stable comparison sort algorithm with expected time $O(N \log N)$, worst case time $O(N \sqrt{N})$, and space requirements 2N. We conjecture that, by using an interpolation search, the expected time can be reduced to $O(N \log \log N)$. By comparison, Quicksort takes expected time $O(N \log N)$, worst case time $O(N^{2})$ and space $N + \log N$. Second, we show that for any fixed $d \geq 2$ a table management algorithm can be constructed that can process a sequence of $N$ instructions chosen from among INSERT, DELETE, SEARCH, and, MIN in worst case time $O(N^{1+1/d})$. Experiments with a version of the algorithms using $d=2$ show a marked improvement over balanced tree schemes for $N$ as large as several thousand. URI: http://hdl.handle.net/1813/7479 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
78-362.ps454.37 kBPostscriptView/Open

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.