A variant of heapsort with almost optimal number of comparisons |
| |
| Affiliation: | 1. Konerulakshmaiah Educational Foundation (KL University), Guntur, Andra Pradesh, India;2. Vivekanandha College of Engineering for Women, Tiruchengode, Namakkal (Dt), Tamilnadu;1. School of Aeronautics and Astronautics, Sichuan University, Chengdu 610064, PR China;2. School of Computer Science and Engineering, Sichuan University, Chengdu 610064, PR China;1. Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China;2. School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China |
| |
| Abstract: | An algorithm, which asymptotically halves the number of comparisons made by the common Heapsort, is presented and analysed in the worst case. The number of comparisons is shown to be (n+1)(log(n+1)+log log(n+1)+1.82)+O(log n) in the worst case to sort n elements, without using any extra space. Quicksort, which usually is referred to as the fastest in-place sorting method, uses 1.38n log n ? O(n) in the average case (see Gonnet (1984)). |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
