Adaptive sorting techniques for nearly reverse sorted lists
Date of Publication
2008
Document Type
Master's Thesis
Degree Name
Master of Science in Computer Science
College
College of Computer Studies
Department/Unit
Computer Science
Thesis Adviser
Nelson Marcos
Defense Panel Member
Rachel Edita O. Roxas
Abstract/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
Abstract Format
html
Language
English
Format
Accession Number
TG04473; CDTG004473
Shelf Location
Archives, The Learning Commons, 12F Henry Sy Sr. Hall
Physical Description
1 v. (various foliations) ; 28 cm. + 1 computer optical disc.
Keywords
Computer algorithms; Sorting (Electronic computers); List processing (Electronic computers)
Upload Full Text
wf_no
Recommended Citation
Go, N. A. (2008). Adaptive sorting techniques for nearly reverse sorted lists. Retrieved from https://animorepository.dlsu.edu.ph/etd_masteral/3728
Note
Cover title