Ching-Kuang Shene
Abstract
Carraway recently published an article [2] describing a sorting algorithm (the sediment sort) for doubly linked lists. He claimed that the sediment sort is one of the fastest and most efficient sorts for linked list, and planned to determine its complexity. In this article, a comparative study will be presented to show that the sediment sort is only a minor variation of the bubble sort which has been known to the computer science community for more than three decades and that the sediment sort is perhaps the slowest algorithm for sorting linked lists.
- 1. Jon Bentley, Programming Pearls, Addison-Wesley, 1986. Google Scholar
- 2. Jim Carraway, Doubly-Linked Opportunities, ACM SIG3C 3C ONLINE, Vol. 3 (1996), No. 1 (January), pp. 9-12. Google ScholarDigital Library
- 3. R. Hoare, Quicksort, The Computer Journal, Vol. 5 (1962), pp. 10-15.Google ScholarCross Ref
- 4. Donald E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, second printing, Addison-Wesley, 1975. Google ScholarDigital Library
- 5. Dalia Motzkin, A Stable Quicksort, Software-Practice and Experience, Vol. 11 (1981), No. 6, pp. 607-611.Google ScholarCross Ref
- 6. Robert Sedgewick, Algorithms in C++, Addison-Wesley, 1992. Google ScholarDigital Library
- 7. Lutz M. Wegner, Sorting a Linked List with Equal Keys, Information Processing Letters, Vol. 15 (1982), No. 5 (December), pp. 205-208.Google ScholarCross Ref
- 8. Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Benjamin/Cummings, 1994. Google ScholarDigital Library
- 9. Niklaus Wirth, Algorithms & Data Structures, Prentice-Hall, 1986. Google ScholarDigital Library
Index Terms
- A comparative study of linked list sorting algorithms
Recommendations
Best sorting algorithm for nearly sorted lists
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 ...
An inverted taxonomy of sorting algorithms
Special section on computer architectureAn alternative taxonomy (to that of Knuth and others) of sorting algorithms is proposed. It emerges naturally out of a top-down approach to the derivation of sorting algorithms. Work done in automatic program synthesis has produced interesting results ...
Measures of Presortedness and Optimal Sorting Algorithms
The concept of presortedness and its use in sorting are studied. Natural ways to measure presortedness are given and some general properties necessary for a measure are proposed. A concept of a sorting algorithm optimal with respect to a measure of ...
Comments