Name
Abstract | ||
|---|---|---|
To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of monotonic partitions. Some sorting strategies that are optimal with respect to these measures of presortedness are presented. The relationships between these new measures of presortedness and other known measures have also been explored. As an application, we carry out the optimality of an adaptive sorting algorithm Skiena'sMelsort. For some special partitioning strategies, we present two sorting algorithms based on Dijkstra'sSmoothsort. Moreover, the optimalities of these two algorithms are demonstrated. By examining the optimalities of sorting algorithms with respect to certain measures of presortedness, we also propose some optimal sorting strategies for one class of measures. Finally, we discuss other types of sorting problems, such as sorting multisets and topological sorting. In particular, we derive an optimal algorithm for sorting multisets and for finding the multiset sizes as well. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/BF01185681 | SODA |
Keywords | DocType | Volume |
Information System,Operating System,Data Structure,Communication Network,Optimal Algorithm | Conference | 29 |
Issue | ISSN | Citations |
3 | 0001-5903 | 0 |
PageRank | References | Authors |
0.34 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |
| Jingsen Chen | 2 | 66 | 9.80 |