AN INVERTED TAXONOMY OF SORTING ALGORITHMS

作     者：MERRITT, SM 

作者机构：School of Computer Science and Information Systems Pace University Graduate Center NY 

出 版 物：《COMMUNICATIONS OF THE ACM》 (美国计算机学会通讯)

年 卷 期：1985年第28卷第1期

页      面：96-99页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：bottom-up top-down transformational programming 

摘      要：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]