Thumbnail
Access Restriction
Subscribed

Author Beus, H. Lynn
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1970
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The information-gathering aspect of sorting is considered from a theoretical viewpoint. A large class, $\textit{R,}$ of sorting algorithms is defined, based on the idea of information use. Properties of this algorithm class are developed, and it is noted that several well-known sorting algorithms are closely related to algorithms in $\textit{R}.$ The Binary Tree Sort is shown to be in $\textit{R}$ and to have unique properties in this class. A vector is defined which characterizes the information-gathering efficiency of the algorithms of $\textit{R}.$ Finally, a more general class of algorithms is defined, and some of the definitions extended to this class. Two intriguing conjectures are given which appear to require graph theory or combinatorial topology for their solution.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1970-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 17
Issue Number 3
Page Count 14
Starting Page 482
Ending Page 495


Open content in new tab

   Open content in new tab
Source: ACM Digital Library