AN INVERTED TAXONOMY of SORTING ALGORITHMS.
Saved in:
| Title: | AN INVERTED TAXONOMY of SORTING ALGORITHMS. |
|---|---|
| Authors: | Horowitz, Ellis, Merritt, Susan M.1 |
| Source: | Communications of the ACM. Jan1985, Vol. 28 Issue 1, p96-99. 4p. 1 Graph. |
| Subjects: | Algorithms, Computer programming, Online algorithms, Sorting (Electronic computers), Electronic data processing |
| Abstract: | An 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 about sorting algorithms that suggest this approach. In particular, all sorts are divided into two categories: hardsplit/easyjoin and easysplit/hardjoin. Quicksort and merge sort, respectively, are the canonical examples in these categories. Insertion sort and selection sort are seen to be instances of merge sort and quicksort, respectively, and sinking sort and bubble sort are in-place versions of insertion sort and selection sort. Such an organization introduces new insights into the connections and symmetries among sorting algorithms, and is based on a higher level, more abstract, and conceptually simple basis. It is proposed as an alternative way of understanding, describing, and teaching sorting algorithms. [ABSTRACT FROM AUTHOR] |
| Copyright of Communications of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 5236501 AccessLevel: 6 PubType: Periodical PubTypeId: serialPeriodical PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: AN INVERTED TAXONOMY of SORTING ALGORITHMS. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Horowitz%2C+Ellis%22">Horowitz, Ellis</searchLink><br /><searchLink fieldCode="AR" term="%22Merritt%2C+Susan+M%2E%22">Merritt, Susan M.</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Communications+of+the+ACM%22">Communications of the ACM</searchLink>. Jan1985, Vol. 28 Issue 1, p96-99. 4p. 1 Graph. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programming%22">Computer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Online+algorithms%22">Online algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Sorting+%28Electronic+computers%29%22">Sorting (Electronic computers)</searchLink><br /><searchLink fieldCode="DE" term="%22Electronic+data+processing%22">Electronic data processing</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: An 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 about sorting algorithms that suggest this approach. In particular, all sorts are divided into two categories: hardsplit/easyjoin and easysplit/hardjoin. Quicksort and merge sort, respectively, are the canonical examples in these categories. Insertion sort and selection sort are seen to be instances of merge sort and quicksort, respectively, and sinking sort and bubble sort are in-place versions of insertion sort and selection sort. Such an organization introduces new insights into the connections and symmetries among sorting algorithms, and is based on a higher level, more abstract, and conceptually simple basis. It is proposed as an alternative way of understanding, describing, and teaching sorting algorithms. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Communications of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=5236501 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 4 StartPage: 96 Subjects: – SubjectFull: Algorithms Type: general – SubjectFull: Computer programming Type: general – SubjectFull: Online algorithms Type: general – SubjectFull: Sorting (Electronic computers) Type: general – SubjectFull: Electronic data processing Type: general Titles: – TitleFull: AN INVERTED TAXONOMY of SORTING ALGORITHMS. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Horowitz, Ellis – PersonEntity: Name: NameFull: Merritt, Susan M. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: Jan1985 Type: published Y: 1985 Identifiers: – Type: issn-print Value: 00010782 Numbering: – Type: volume Value: 28 – Type: issue Value: 1 Titles: – TitleFull: Communications of the ACM Type: main |
| ResultId | 1 |
