SORTING AND SEARCHING

SORTING-INTRODUCTION
Sorting is a technique of organizing the data. It is a process of arranging the records,
either in ascending or descending order i.e. bringing some order lines in the data. Sort
methods are very important in Data structures.
Sorting can be performed on any one or combination of one or more attributes present in
each record. It is very easy and efficient to perform searching, if data is stored in sorting
order. The sorting is performed according to the key value of each record. Depending up on
the makeup of key, records can be stored either numerically or alphanumerically. In
numerical sorting, the records arranged in ascending or descending order according to the
numeric value of the key.
Let A be a list of n elements A1, A2, A3 …………………….An in memory. Sorting A refers to the
operation of rearranging the contents of A so that they are increasing in order, that is, so
that A1 <=A2 <=A3 <=…………….<=An. Since A has n elements, there are n! Ways that the
contents can appear in A. these ways corresponding precisely to the n! Permutations of
1,2,3,………n. accordingly each sorting algorithm must take care of these n! Possibilities.

Ex: suppose an array DATA contains 8elements as follows:

DATA: 70, 30,40,10,80,20,60,50.
After sorting DATA must appear in memory as follows:
DATA: 10 20 30 40 50 60 70 80
Since DATA consists of 8 elements, there are 8!=40320 ways that the numbers
10,20,30,40,50,60,70,80 can appear in DATA.
The factors to be considered while choosing sorting techniques are:
 Programming Time
 Execution Time
 Number of Comparisons
 Memory Utilization
 Computational Complexity

Types of Sorting Techniques:

Sorting techniques are categorized into 2 types. They are Internal Sorting and External
Sorting.
Internal Sorting: Internal sorting method is used when small amount of data has to be
sorted. In this method , the data to be sorted is stored in the main memory (RAM).Internal
sorting method can access records randomly. EX: Bubble Sort, Insertion Sort, Selection Sort,
Shell sort, Quick Sort, Radix Sort, Heap Sort etc.
External Sorting: Extern al sorting method is used when large amount of data has to be
sorted. In this method, the data to be sorted is stored in the main memory as well as in the
secondary memory such as disk. External sorting methods an access records only in a
sequential order. Ex: Merge Sort, Multi way Mage Sort.

Complexity of sorting Algorithms: The complexity of sorting algorithm measures the

running time as a function of the number n of items to be stored. Each sorting algorithm S
will be made up of the following operations, where A1, A2, A3 …………………….An contain the
items to be sorted and B is an auxiliary location.

37
  Comparisons, which test whether Ai < Aj or test whether Ai <B.
 Interchanges which switch the contents of Ai and Aj or of Ai and B.
 Assignment which set B: Ai and then set Aj := B or Aj:= Ai
Normally, the complexity function measures only the number of comparisons, since the
number of other operations is at most a constant factor of the number of comparisons.

SELECTION SORT
In selection sort, the smallest value among the unsorted elements of the array is
selected in every pass and inserted to its appropriate position into the array. First, find the
smallest element of the array and place it on the first position. Then, find the second
smallest element of the array and place it on the second position. The process continues
until we get the sorted array. The array with n elements is sorted by using n-1 pass of
selection sort algorithm.
 In 1st pass, smallest element of the array is to be found along with its
index pos. then, swap A[0] and A[pos]. Thus A[0] is sorted, we now have n
-1 elements which are to be sorted.
 In 2nd pas, position pos of the smallest element present in the sub-array
A[n-1] is found. Then, swap, A[1] and A[pos]. Thus A[0] and A[1] are sorted,
we now left with n-2 unsorted elements.
 In n-1th pass, position pos of the smaller element between A[n-1] and A[n-
2] is to be found. Then, swap, A[pos] and A[n-1].

Therefore, by following the above explained process, the elements

A[0], A[1], A[2], ... , A[n-1] are sorted.

Example: Consider the following array with 6 elements. Sort the elements of the array
by using selection sort.
A = {10, 2, 3, 90, 43, 56}.

Pass Pos A[0] A[1] A[2] A[3] A[4] A[5]

1 1 2 10 3 90 43 56
2 2 2 3 10 90 43 56
3 3 2 3 10 90 43 56
4 4 2 3 10 43 90 56
5 5 2 3 10 43 56 90

Sorted A = {2, 3, 10, 43, 56, 90}

Complexity
Complexity Best Average Case Worst Case
Case
Time Ω(n) 2 2
θ(n ) o(n )

Space o(1)

38
Algorithm

SELECTION SORT (ARR, N)

Step 1: Repeat Steps 2 and 3 for K = 1 to N-1

Step 2: CALL SMALLEST(A, K, N, POS)

Step 3: SWAP A[K] with

A[POS] [END OF LOOP]
Step 4: EXIT

LINEAR SEARCH
The Linear search or Sequential Search is most simple searching method. It does
not expect the list to be sorted. The Key which to be searched is compared with each
element of the list one by one. If a match exists, the search is terminated. If the end of the
list is reached, it means that the search has failed and the Key has no matching element in
the list.
Ex: consider the following Array A
23 15 18 17 42 96 103
Now let us search for 17 by Linear search. The searching starts from the first position.
Since A[0] ≠17.
The search proceeds to the next position i.e; second position A[1] ≠17.
The above process continuous until the search element is found such as A[3]=17.
Here the searching element is found in the position 4.

Algorithm: LINEAR(DATA, N,ITEM, LOC)

Here DATA is a linear Array with N elements. And ITEM is a given item of information. This
algorithm finds the location LOC of an ITEM in DATA. LOC=-1 if the search is unsuccessful.
Step 1: Set DATA[N+1]=ITEM
Step 2: Set LOC=1
Step 3: Repeat while (DATA [LOC] != ITEM)
Set LOC=LOC+1
Step 4: if LOC=N+1 then
Set LOC= -1.
Step 5: Exit

Advantages:
 It is simplest known technique.
 The elements in the list can be in any order.
Disadvantages:
This method is in efficient when large numbers of elements are present in list because time
taken for searching is more.
Complexity of Linear Search: The worst and average case complexity of Linear search is
O(n), where ‘n’ is the total number of elements present in the list.

BINARY SEARCH
Suppose DATA is an array which is stored in increasing order then there is an extremely
efficient searching algorithm called “Binary Search”. Binary Search can be used to find the
location of the given ITEM of information in DATA.
Working of Binary Search Algorithm:
During each stage of algorithm search for ITEM is reduced to a segment of elements of
DATA[BEG], DATA[BEG+1], DATA[BEG+2],……………………… DATA[END].
Here BEG and END denotes beginning and ending locations of the segment under
considerations. The algorithm compares ITEM with middle element DATA[MID] of a
segment, where MID=[BEG+END]/2. If DATA[MID]=ITEM then the search is successful. and
we said that LOC=MID. Otherwise a new segment of data is obtained as follows:
i. If ITEM<DATA[MID] then item can appear only in the left half of the segment.
DATA[BEG], DATA[BEG+1], DATA[BEG+2]
So we reset END=MID-1. And begin the search again.

ii. If ITEM>DATA[MID] then ITEM can appear only in right half of the segment
i.e. DATA[MID+1], DATA[MID+2],……………………DATA[END].
So we reset BEG=MID+1. And begin the search again.
Initially we begin with the entire array DATA i.e. we begin with BEG=1 and END=n
Or
BEG=lb(Lower Bound)
END=ub(Upper Bound)
If ITEM is not in DATA then eventually we obtained END<BEG. This condition signals that the
searching is Unsuccessful.
The precondition for using Binary Search is that the list must be sorted
one. Ex: consider a list of sorted elements stored in an Array A is

Let the key element which is to be searched is 35.

Key=35
The number of elements in the list n=9.
Step 1: MID= [lb+ub]/2
=(1+9)/2
=5
 Key<A[MID]
i.e. 35<46.
So search continues at lower half of the array.
Ub=MID-1
=5-1
= 4.

Step 2: MID= [lb+ub]/2

=(1+4)/2
=2.

Key>A[MID]
i.e. 35>12.
So search continues at Upper Half of the array.
Lb=MID+1
=2+1
= 3.

Step 3: MID= [lb+ub]/2

=(3+4)/2
=3.

Key>A[MID]
i.e. 35>30.
So search continues at Upper Half of the array.
Lb=MID+1
=3+1
= 4.
Step 4: MID= [lb+ub]/2
=(4+4)/2
=4.
ALGORITHM:
BINARY SEARCH[A,N,KEY]
Step 1: begin
Step 2: [Initilization]
Lb=1; ub=n;
Step 3: [Search for the ITEM]

Repeat through step 4,while Lower bound is less than Upper Bound.
Step 4: [Obtain the index of middle value]
MID=(lb+ub)/2
Step 5: [Compare to search for ITEM]
If Key<A[MID] then
Ub=MID-1
Other wise if Key >A[MID] then
Lb=MID+1
Otherwise write “Match Found”
Return Middle.
Step 6: [Unsuccessful Search]
write “Match Not Found”
Step 7: Stop.

Advantages: When the number of elements in the list is large, Binary Search executed faster
than linear search. Hence this method is efficient when number of elements is large.

Disadvantages: To implement Binary Search method the elements in the list must be in
sorted order, otherwise it fails.
Define sorting? What is the difference between internal and external sorting methods?
Ans:- Sorting is a technique of organizing data. It is a process of arranging the elements
either may be ascending or descending order, ie; bringing some order lines with data.

Internal sorting External sorting

1. Internal Sorting takes place in the main 1. External sorting is done with additional
memory of a computer. external memory like magnetic tape or hard
disk
2. The internal sorting methods are applied 2. The External sorting methods are applied
to small collection of data. only when the number of data elements to
be sorted is too large.
3. Internal sorting takes small input 3. External sorting can take as much as large
input.
4. It means that, the entire collection of data 4. External sorting typically uses a sort-
to be sorted in small enough that the sorting merge strategy, and requires auxiliary
can take place within main memory. storage.
5. For sorting larger datasets, it may be 5. In the sorting phase, chunks of data small
necessary to hold only a chunk of data in enough to fit in main memory are read,
memory at a time, since it wont all fit. sorted, and written out to a temporary file.
6. Example of Internal Sorting algorithms are 6. Example of External sorting algorithms
:- Bubble Sort, Internal Sort, Quick Sort, are: - Merge Sort, Two-way merge sort.
Heap Sort, Binary Sort, Radix Sort, Selection
sort.
7. Internal sorting does not make use of 7. External sorting make use of extra
extra resources. resources.