Curtis R. Cook
Abstract
Straight Insertion Sort, Shellsort, Straight Merge Sort, Quickersort, and Heapsort are compared on nearly sorted lists. The ratio of the minimum number of list elements which must be removed so that the remaining portion of the list is in order to the size of the list is the authors' measure of sortedness. Tests on randomly generated lists of various combinations of list length and small sortedness ratios indicate that Straight Insertion Sort is best for small or very nearly sorted lists and that Quickersort is best otherwise. Cook and Kim also show that a combination of the Straight Insertion Sort and Quickersort with merging yields a sorting method that performs as well as or better than either Straight Insertion Sort or Quickersort on nearly sorted lists.
- 1 Boothroyd, J. Algorithm 201: Shellsort. Comm. ACM 6, 8 (Aug. 1963), 445.Google Scholar
- 2 Boothroyd, J. Algorithm 207: Stringsort. Comm. ACM6, 10 (Oct. 1963), 615. Google ScholarDigital Library
- 3 Elson, M. Data Structures. Sci. Res. Associates, Chicago, IlL, 1975. An excellent data structures textbook with a chapter on sorting.Google Scholar
- 4 Floyd, R.W. Algorithm 245: TREE- SORT3. Comm. ACM 7, 12 (Dec. 1964), 701. Google ScholarDigital Library
- 5 Fredman, M.L. On computing the length of longest increasing subsequences. Discrete Math. 11 (1975), 29-35. Describes a simple algorithm using order n log n comparisons to fred the length of a longest increasing subsequence in a sequence of n distinct elements. The algorithm is also shown to be the best possible.Google ScholarDigital Library
- 6 Hoare, C.A.R. Algorithm 64: Quicksort. Comm. ACM 4, 7 (July 1961), 321. Google ScholarDigital Library
- 7 Knuth, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. The complete reference book on sorting and searching. Google ScholarDigital Library
- 8 Loeser, R. Some performance tests of "quicksort" and descendants. Comm. A CM 17, 3 (March 1974), 143-152. Reports results of an empirical study that compared Quicksort, two of its descendants (Quickersort and qsort), Shellsort, strmgsort, and Treesort. Google ScholarDigital Library
- 9 MacLaren, M.D. Internal sorting by radix plus sifting. J. ACM 13, 3 (July 1966), 404-- 411. Describes a sorting algorithm that is a combination of the radix and Straight Insertion Sorts. Author chose the Straight Insertion Sort because it works well "when the records are almost in order, as they will be after the radix sort." Google ScholarDigital Library
- 10 Martin, W.A. Sorting. Comptng. Surveys 3, 4 (Dec. 1971), 147-174. A highly recommended, readable survey of sorting algorithms. Google ScholarDigital Library
- 11 Melhorn, K. Sorting presorted files. In Theoretical Computer Science 4th GI Conf., K. Weihrauch, Ed., Lecture Notes in Computer Science, Vol. 67, Springer-Verlag, Berlin, 1979, pp. 199-212. This article assumes a knowledge of AVL-trees. It presents a new sorting algorithm for nearly sorted lists that uses a Straight Insertion Sort for rapid insertion in an AVL-treelike data structure. Google ScholarDigital Library
- 12 Scowen, R.S. Algorithm 271: Quickersort. Comm. ACM 8, 11 (Nov. 1965), 669-670. Google ScholarDigital Library
- 13 vanEmden, M.H. Algorithm 402: qsort. Comm. ACM 13, I l (Nov. 1970), 693-694.Google ScholarDigital Library
- 14 Williams, J.W.J. Algorithm 232: Heapsort. Comm. ACM 7, 6 (June 1964), 347-348.Google Scholar
Index Terms
- Best sorting algorithm for nearly sorted lists
Recommendations
Some performance tests of “quicksort” and descendants
Detailed performance evaluations are presented for six ACM algorithms: quicksort (No. 64), Shellsort (No. 201), stringsort (No. 207), “TREESORT3” (No. 245), quickersort (No. 271), and qsort (No. 402). Algorithms 271 and 402 are refinements of algorithm ...
A top down approach to sorting
Proceedings of the 12th SIGCSE symposium on Computer science educationA top-down approach is presented for the derivation of, and corresponding exposition of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms which suggest this approach. In particular ...
A top down approach to sorting
SIGCSE '81: Proceedings of the twelfth SIGCSE technical symposium on Computer science educationA top-down approach is presented for the derivation of, and corresponding exposition of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms which suggest this approach. In particular ...
Comments