Adaptive sorting techniques for nearly reverse sorted lists
There are many sorting algorithms, which are adaptive on different types of disorder measurements. Existing adaptive algorithms, which uses Runs as a division protocol, performs well on low runs percentages. However, the adaptiveness reduces whenever the given list is in a nearly reverse sorted mann...
Saved in:
| Main Author: | |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Animo Repository
2008
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/etd_masteral/3728 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Language: | English |
| Summary: | There are many sorting algorithms, which are adaptive on different types of disorder measurements. Existing adaptive algorithms, which uses Runs as a division protocol, performs well on low runs percentages. However, the adaptiveness reduces whenever the given list is in a nearly reverse sorted manner; in short, lists of high run percentages. Although Enc-adaptive sorting algorithms like Melsort solves this problem, it runs at O(n2); which puts its practicality in question. In this paper, we present possible modifications of natural mergesort by incorporating techniques like utilization of Reverse Runs and Loose Enc rules as division protocols. Both methods have shown to be O(nlogn) and tend to have less comparisons against existing Run-adaptive sorting algorithms on Run percentages of 70% or higher for array sizes ranging from 50 to 50,000. Keywords: Algorithms, Theory |
|---|