Page 239 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes The difference lies in the fact that the fi rst method moves data only over small distances in the
process of sorting, whereas the second method moves data over large distances, so that items
settle into the proper order sooner, thus resulting in fewer comparisons. Performance of a sorting
algorithm can also depend on the degree of order already present in the data.
There are two basic categories of sorting methods: Internal Sorting and External Sorting. Internal
sorting is applied when the entire collection of data to be sorted is small enough so that the sorting
can take place within the main memory. The time required to read or write is not considered to be
significant in evaluating the performance of internal sorting methods. External sorting methods

are applied to larger collection of data which reside on secondary devices. Read and write access
times are a major concern in determining sorting performances of such methods.
Searching is the process of looking for something: Finding one piece of data that has been stored
within a whole group of data. It is often the most time-consuming part of many computer
programs. There are a variety of methods, or algorithms, used to search for a data item, depending
on how much data there is to look through, what kind of data it is, what type of structure the data
is stored in, and even where the data is stored - inside computer memory or on some external
medium.
Till now, we have studied a variety of data structures, their types, their use and so on. In this
chapter, we will concentrate on some techniques to search a particular data or piece of information
from a large amount of data. There are basically two types of searching techniques, Linear or
Sequential Search and Binary Search.
Searching is very common task in day-to-day life, where we are involved some or other time, in

searching either for some needful at home or office or market, or searching a word in dictionary.
In this chapter, we see that if the things are organised in some manner, then search becomes

efficient and fast.
All the above facts apply to our computer programs also. Suppose we have a telephone directory
stored in the memory in an array which contains Name and Numbers. Now, what happens if we
have to find a number? The answer is search that number in the array according to name (given).

If the names were organised in some order, searching would have been fast.

12.1 Internal Sorting

The function of sorting or ordering a list of objects according to some linear order is so fundamental
that it is ubiquitous in engineering applications in all disciplines. There are two broad categories of
sorting methods: Internal sorting takes place in the main memory, where we can take advantage
of the random access nature of the main memory; external sorting is necessary when the number
and size of objects are prohibitive to be accommodated in the main memory.

Problem

1. Given records r1, r2,..., rn, with key values k1, k2,..., kn, produce the records in the order
ri1, ri2,..., rin,
such that
ki1 ≤ ki2 ≤ ... ≤ kin
2. The complexity of a sorting algorithm can be measured in terms of
(a) number of algorithm steps to sort n records
(b) number of comparisons between keys (appropriate when the keys are long character
strings)
(c) number of times records must be moved (appropriate when record size is large)

234 LOVELY PROFESSIONAL UNIVERSITY