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

Note

Cover title

Language

English

Format

Print

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

This document is currently not available here.

Share

COinS