Algorithms for sorting nearly sorted lists
| dc.contributor.author | Wright, J. | |
| dc.date.accessioned | 2016-08-31T00:41:21Z | |
| dc.date.available | 2016-08-31T00:41:21Z | |
| dc.date.issued | 1986 | en |
| dc.description.abstract | The following five algorithms for sorting in situ are examined: linear insertion sort, cksort, natural mergesort, ysort and smoothsort. Quicksort and heapsort are also considered although they are not discussed in detail. The algorithms have been implemented and compared, with particular emphasis being placed on the algorithms' efficiency when the lists are nearly sorted. Five measures of sortedness are investigated. These are sortedness ratio, number of inversions, longest ascending sequence, number of ascending sequences, and number of exchanges. The sortedness ratio is chosen as a basis for comparison between these measures and is used in experiments on the above algorithms. Improvements to cksort and ysort are suggested, while modifications to smoothsort and linear insertion sort failed to improve the efficiency of these algorithms. | en |
| dc.identifier.uri | http://hdl.handle.net/10092/12652 | |
| dc.language.iso | en | |
| dc.publisher | University of Canterbury | en |
| dc.rights | All Rights Reserved | en |
| dc.rights.uri | https://canterbury.libguides.com/rights/theses | |
| dc.subject.anzsrc | Field of Research::08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics::080201 - Analysis of Algorithms and Complexity | en |
| dc.title | Algorithms for sorting nearly sorted lists | en |
| dc.type | Discussion / Working Papers | |
| uc.college | Faculty of Engineering | |
| uc.department | School of Engineering | en |