DESIGN AND IMPLEMENTATION OF RESOURCE SORTING ALGORITHMS FOR RESEARCH LIBRARY OPERATION

Description

ABSTRACT

One of the basic problems in computer science is to arrange the items in lexicographic order. Sorting is one of the major research topic. There are number of sorting algorithms.

This paper presents the implementation and detailed analysis of library sort. Library sort is also called gaped insertion sort. It is a sorting algorithm that uses insertion sort with gaps. Time taken by insertion sort is O (n2) because each insertion takes O (n) time; and library sort has insertion time O (log n) with high probability. Total running time of library sort is O (n log n) time with high probability. Library sort has better run time than insertion sort, but the library sort also has some issues. The first issue is the value of gap which is denoted by ‘ε’, the range of gap is given, but it is yet to be implemented to check that given range is satisfying the concept of library sort algorithm. The second issue is re-balancing which accounts the cost and time of library sort algorithm. The third issue is that, only a theoretical concept of library sort is given, but the concept is not implemented. So, to overcome these issues of library sort, in this paper, we have implemented the concept of library sort and done the detailed experimental analysis of library sort algorithm, and measure the performance of library sort algorithm on a data set.

TABLE OF CONTENTS

 TITLE PAGE

APPROVAL PAGE

DEDICATION

ACKNOWLEDGEMENT

ABSTRACT

TABLE OF CONTENT

CHAPTER ONE

• INTRODUCTION
• SIGNIFICANCE OF THE STUDY
• PROPERTIES OF SORTING ALGORITHMS
• CLASSIFICATION OF SORTING ALGORITHMS USED IN COMPUTER SCIENCE
• AIMS OF THE ALGORITHMS

CHAPTER TWO

2.0      LITERATURE REVIEW
2.1      REVIEW OF THE STUDY
2.2     OVERVIEW OF THE STUDY
2.3     HISTORICAL BACKGROUND OF THE STUDY

2.4     CLASSIFICATION SORTING ALGORITHMS

2.5      POPULAR SORTING ALGORITHMS

2.6     MEMORY USAGE PATTERNS AND INDEX SORTING

CHAPTER THREE

3.0      METHODOLOGY

3.1     LIBRARY SORT ALGORITHM

3.2    EXECUTION TIME TESTING OF LIBRARY SORT ON A DATA SET

3.3    EXISTING BUBBLE SORT ALGORITHM

3.4    PROPOSED OPTIMIZED BUBBLE SORT ALGORITHM

3.5   DATA FLOW REPRESENTATION

3.6   IMPLEMENTATIONCHAPTER ONE

 

1.0                                                        INTRODUCTION

In computer science, sorting algorithm [2] is an algorithm that sorts the list of items in a certain order;

Insertion sort iterates, takes one input element with each repetition, and put it into the sorted output list. Repeat the process until no input elements remains unprocessed. Insertion sort [10] is less efficient on large number of items as it takes O (n2) time in worst case, and the best case of insertion sorting occurs when data is in sorted manner and it is O (n) in best case. Insertion sort is an adaptive [3] sorting algorithm; it is also a stable sorting algorithm [4].

Michael A. Bender proposed the library sort algorithm or gapped insertion sort [1]. Library sort is a sorting algorithm that comes by an insertion sort but there is a space after each element in the array to accelerate subsequent insertions. Library sort is an adaptive sorting and also a stable sorting algorithm [9]. If we leave more space, the fewer elements we move on insertions. The author achieves the O (log n) insertions with high probability using the evenly distributed gap, and the algorithm runs O (n log n) with high probability. O (n log n) is better than O (n2). But the library sort also has some issues. The first issue is the value of gap, range of gap is given, but it is yet to be implemented after implementation, we can only decide that given range is satisfying the concept of library sort. The second issue is re-balancing, re-balancing has done after 2i elements in library sort, but it also accounts cost and time of library sort algorithm. The third issue is that only a theoretical concept of library sort is given by Bender et al but he has not implemented it. So, in this paper to overcome these issues of library sort, we have implemented the concept, done the detailed experimental analysis and we measure the performance on a data set. The application of leaving gaps for insertions in a data structure is used by Itai, Konheim, and

Rodeh [8]. This idea has found recent application in external memory and cache-oblivious algorithms in the packed memory structure of Bender, Demaine and Farach-Colton [1] and later used in [6, 7]. The remainder of this paper is organized as follows. The detail of library sort algorithm is given in section 2 and the time complexity based testing using the data set is done in section 3. The space complexity based testing on a data set is done in section 4 [13]. The re-balancing based testing is done in section 5. We analysis the performance of library sort in section 6 and present the conclusion and future work with a few comments in section 7 and 8.

1.1                                           SIGNIFICANCE OF THE STUDY

Sorting arranges data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order. The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Following are some of the examples of sorting in real-life scenarios −

• Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily.
• Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.

1.2                                 PROPERTIES OF SORTING ALGORITHMS

All sorting algorithms share the goal of outputting a sorted list, but the way that each algorithm goes about this task can vary. When working with any kind of algorithm, it is important to know how fast it runs and in how much space it operates — in other words, its time and space complexity. As shown in the section above, comparison-based sorting algorithms have a time complexity of Ω(ῃ log ῃ), meaning the algorithm can’t be faster than ῃ log ῃ. However, usually, the running time of algorithms is discussed​ in terms of Big O(ῃ log ῃ), and not Omega. For example, if an algorithm had a worst-case running time of O, then it is guaranteed that the algorithm will never be slower than O(ῃ log ῃ) , and if an algorithm has an average-case running time of O(n² ), then on average, it will not be slower than O(n² ).

The running time describes how many operations an algorithm must carry out before it completes. The space complexity describes how much space must be allocated to run a particular algorithm. For example, if an algorithm takes in a list of size , and for some reason makes a new list of size for each element in , the algorithm needs space.

 

1.3 CLASSIFICATION OF SORTING ALGORITHMS USED IN COMPUTER SCIENCE

• Computational complexity (worst, average and best behavior) of element comparisons in terms of the size of the list.

For typical sorting algorithms good behavior is O(n logn) and bad behavior is O(n2).

• Memory usage (and use of other computer resources). In particular, some sorting algorithms are “in place”. This means that they need only O(1) memory beyond the items being sorted and they don’t need to create auxiliary locations for data to be temporarily stored, as in other sorting algorithms

.

• Recursion: Some algorithms are either recursive or non-recursive, while others may be both (e.g., merge sort).
• Stability: stable sorting algorithms maintain the relative order of records with equal keys (i.e., values).

 

1.4                                             AIMS OF THE ALGORITHMS

The algorithm had several aims:

• To increase the Speed of sorting materials in library.
• Good memory utilization. The number of elements that can be sorted should closely approach the physical limits of the machine.
• In order for the algorithm to be truly general purpose the only operator that will be assumed is binary comparison. This rule out methods such as radix sort [2, 3].
• To obtain good memory utilization when sorting small elements linked lists are avoided. Thus, the lists of elements referred to below are implemented using arrays, without any storage overhead for pointers.

 

1.4                                                         PROJECT ORGANISATION

The work is organized as follows: chapter one discuses the introductory part of the work,   chapter two presents the literature review of the study,  chapter three describes the methods applied, chapter four discusses the results of the work, chapter five summarizes the research outcomes and the recommendations.