A class of sorting algorithms based on Quicksort

ABSTRACT

Bsort, a variation of Quicksort, combines the interchange technique used in Bubble sort with the Quicksort algorithm to improve the average behavior of Quicksort and eliminate the worst case situation of O(n2) comparisons for sorted or nearly sorted lists. Bsort works best for nearly sorted lists or nearly sorted in reverse.

REFERENCES

• 1: Curtis R. Cook , Do Jin Kim, Best sorting algorithm for nearly sorted lists, Communications of the ACM, v.23 n.11, p.620-624, Nov. 1980 [doi>10.1145/359024.359026]
• 2: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• 3: Hoare. C.A.R. Quicksort. Computer 1: 5,4 (Apr. 1962), 10-15.
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: Rudolf Loeser, Some performance tests of “quicksort” and descendants, Communications of the ACM, v.17 n.3, p.143-152, March 1974 [doi>10.1145/360860.360870]
• 6: Rudolf Loeser, Survey on Algorithms 347, 426, and Quicksort, ACM Transactions on Mathematical Software (TOMS), v.2 n.3, p.290-299, Sept. 1976 [doi>10.1145/355694.355702]
• 7: Motzkin. D. A stable Quicksort. Softm. Pratt. Exper. 11, 6 Uune 1981), 607-611.
• 8: Motzkin. D. Meansort. Commun. ACA4 26,4 (Apr. 1983), 250-251. This article describes a sorting algorithm based on Quicksort called Meansort where the mean value of each file controls the partitioning process. Results of an empirical study comparing Meansort and Quicksort are presented. Further information on this article appears in the Technical Correspondence section of Commun. ACM 27, 7 (July 1984). 719-722.
• 9: R. S. Scowen, Algorithm 271: quickersort, Communications of the ACM, v.8 n.11, p.669-670, Nov. 1965 [doi>10.1145/365660.365678]
• 10: Sedgewick, R. Quicksort with equal keys. SIAM J. Comput. 6.2 oune 1977), 240-267.
• 11: Richard C. Singleton, Algorithm 347: an efficient algorithm for sorting with minimal storage [M1], Communications of the ACM, v.12 n.3, p.185-186, March 1969 [doi>10.1145/362875.362901]
• 12: M. H. van Emden, Algorithms 402: Increasing the efficiency of quicksort, Communications of the ACM, v.13 n.11, p.693-694, Nov 1970 [doi>10.1145/362790.362803]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Measurement, Performance, Theory