article

Free access

Pracniques: Meansort

Author:

Dalia MotzkinAuthors Info & Claims

Communications of the ACM, Volume 26, Issue 4

Pages 250 - 251

https://doi.org/10.1145/2163.358088

Published: 01 April 1983 Publication History

PDF eReader

Abstract

This paper presents an efficient algorithm based on Quicksort. The Quicksort algorithm is known to be one of the most efficient sorting techniques; however, one of the drawbacks of this method is its worst case situation of 0 (n²) comparisons. The algorithm presented here improves the average behavior of Quicksort and reduces the occurrence of worst case situations.

References

[1]

Dewar, Robert B.K. A stable minimum storage algorithm. Information Processing Letts. 2 (April 1974) 162-164.

Crossref

Google Scholar

[2]

Hoare, C.A.R. Partition (Algorithm 83); Quicksort (Algorithm 64); and Find (Algorithm 65). Comm. ACM 4, 7 (July 1961) 321-322.

Digital Library

Google Scholar

[3]

Hoare, C.A.R. Quicksort. Computer T. 5, 4 (April 1982) 10-15.

Google Scholar

[4]

Horowitz E. and Sahni, S. Fundamentals of Data Structures. Computer Science Press, California, 1976, pp. 347-350.

Google Scholar

[5]

Knuth, D.E. Sorting and searching. In The Art of Computer Programming 3. Addlson-Wesley, Reading, MA, 1972.

Google Scholar

[6]

Loeser, R. Some performance tests of "quicksort" and "descendents." Comm. ACM 17, 3, (March 1974) 143-152.

Digital Library

Google Scholar

[7]

Loeser, R. Survey on Algorithms 34, 422, and Quicksort. ACM Trans. Mathematical Software. 2, 3, (Sept. 1978) 290-299.

Digital Library

Google Scholar

[8]

Motzkin, D. A stable Quicksort. Software Practice and Experience. 11, 6 (June 1981) 607-611.

Google Scholar

[9]

Scowen, R.D. Quickersort (Algorithm 271). Comm. ACM 8, 11 (Nov. 1965) 669-670.

Digital Library

Google Scholar

[10]

Sedgewick, R. Quicksort with equal keys. SIAM l. Comput. 6, 2 (June 1977) 240-267.

Google Scholar

[11]

Sedgewick, R. The analysis of Quicksort programs. Aeto Informotica 7, (1977) 327-355.

Digital Library

Google Scholar

[12]

Singleton, R.C. An efficient algorithm for sorting with minimal storage (Algorithm 347) Comm. AGM 12 3, (March 1969) 185-187.

Digital Library

Google Scholar

[13]

vanEmden, M.N. Increasing the efficiency of quicksort (Algorithm 402). Comm. ACM 13 11, (Nov. 1970) 693-694.

Digital Library

Google Scholar

Cited By

View all

Mallya SMahesh K(2009)Ssort: Peak Analysis for Efficient String SortingProceedings of the European Computing Conference10.1007/978-0-387-85437-3_37(389-398)Online publication date: 28-Feb-2009
https://doi.org/10.1007/978-0-387-85437-3_37
Podgorelec DKlajnšek G(2005)Acceleration of sweep-line technique by employing smart quicksortInformation Sciences: an International Journal10.1016/j.ins.2004.07.002169:3-4(383-408)Online publication date: 1-Feb-2005
https://dl.acm.org/doi/10.1016/j.ins.2004.07.002
Cunto WGonnet GMunro JPoblete P(1991)Fringe analysis for Extquick: Anin situ distributive external sorting algorithmInformation and Computation10.1016/0890-5401(91)90007-O92:2(141-160)Online publication date: Jun-1991
https://doi.org/10.1016/0890-5401(91)90007-O
Show More Cited By

Index Terms

Pracniques: Meansort
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Efficient sample sort and the average case analysis or PEsort

The purpose of the paper is twofold. First, we want to search for a more efficient sample sort. Secondly, by analyzing a variant of Samplesort, we want to settle an open problem: the average case analysis of Proportion Extend Sort (PEsort for short). An ...
Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 26, Issue 4

April 1983

68 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2163

Editor:
Peter J. Denning
Purdue Univ., West Lafayette, IN

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1983

Published in CACM Volume 26, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
570
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mallya SMahesh K(2009)Ssort: Peak Analysis for Efficient String SortingProceedings of the European Computing Conference10.1007/978-0-387-85437-3_37(389-398)Online publication date: 28-Feb-2009
https://doi.org/10.1007/978-0-387-85437-3_37
Podgorelec DKlajnšek G(2005)Acceleration of sweep-line technique by employing smart quicksortInformation Sciences: an International Journal10.1016/j.ins.2004.07.002169:3-4(383-408)Online publication date: 1-Feb-2005
https://dl.acm.org/doi/10.1016/j.ins.2004.07.002
Cunto WGonnet GMunro JPoblete P(1991)Fringe analysis for Extquick: Anin situ distributive external sorting algorithmInformation and Computation10.1016/0890-5401(91)90007-O92:2(141-160)Online publication date: Jun-1991
https://doi.org/10.1016/0890-5401(91)90007-O
Lins CLins C(1990)SortingThe Modula-2 Software Component Library10.1007/978-1-4684-6371-2_4(23-55)Online publication date: 1990
https://doi.org/10.1007/978-1-4684-6371-2_4
Wainwright RDavis PMcClintock V(1987)Quicksort algorithms with an early exit for sorted subfilesProceedings of the 15th annual conference on Computer Science10.1145/322917.322946(183-190)Online publication date: 1-Feb-1987
https://dl.acm.org/doi/10.1145/322917.322946
Skaredoff M(1987)Sorting efficiencyJournal of Clinical Monitoring10.1007/BF016959453:3(201-209)Online publication date: Jul-1987
https://doi.org/10.1007/BF01695945
Tech Correspondence C(1986)Technical correspondenceCommunications of the ACM10.1145/5684.31561829:4(331-335)Online publication date: 1-Apr-1986
https://dl.acm.org/doi/10.1145/5684.315618
van der Nat MVerrijn-Stuart A(1986)Analysing a class of distributive partitioning sort algorithmsScience of Computer Programming10.1016/0167-6423(86)90003-17:C(23-33)Online publication date: 1-Jun-1986
https://dl.acm.org/doi/10.1016/0167-6423%2886%2990003-1
Motzkin DKapenga J(1984)Technical Correspondence—MEANSORT (April 1983)Communications of the ACM10.1145/358105.138710927:7(719-722)Online publication date: 1-Jul-1984
https://dl.acm.org/doi/10.1145/358105.1387109

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Efficient sample sort and the average case analysis or PEsort

Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

Some performance tests of “quicksort” and descendants

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations