4931-Grace college of engineering
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
BE- Electrical and Electronics Engineering
&
BE- Electronics and Communication Engineering
Anna University Regulation: 2021
CS3353 – C Programming and data structures
II Year / III Semester
Question bank
Unit- V SORTING AND SEARCHING TECHNIQUES
Prepared By,
Rebecca Fernando I.M.S.B, AP/CSE
cs3353_cds
lOMoARcPSD|47265940
4931-Grace College of engineering
UNIT V
SORTING AND SEARCHING TECHNIQUES
1 Define sorting
Sorting arranges the numerical and alphabetical data present in a list in a
specific order or sequence. There are a number of sorting techniques
available. The algorithms can be chosen based on the following factors
● Size of the data structure
● Algorithm efficiency
Programmer’s knowledge of the technique
2 Mention the types of sorting
● Internal sorting
● External sorting
3 What do you mean by internal and external sorting?
An internal sort is any data sorting process that takes place entirely within
the main memory of a computer. This is possible whenever the data to
be sorted is small enough to all be held in the main memory.
External sorting is a term for a class of sorting algorithms that can handle
massive amounts of data. External sorting is required when the data
being sorted do not fit into the main memory of a computing device
(usually RAM) and instead they
must reside in the slower external memory (usually a hard drive).
4 How the insertion sort is done with the array?
It sorts a list of elements by inserting each successive element in the
previously sorted
Sub list.
Consider an array to be sorted A[1],A[2],….A[n]
51
CS3353_CDS
lOMoARcPSD|47265940
4931-Grace College of engineering
a. Pass 1: A[2] is compared with A[1] and placed them in sorted order.
b. Pass 2: A[3] is compared with both A[1] and A[2] and inserted at an appropriate
place. This makes A[1], A[2],A[3] as a sorted sub array.
c. Pass n-1: A[n] is compared with each element in the sub array
A [1], A [2] …A [n-1] and inserted at an appropriate position.
5 what is insertion sort? How many passes are required for theelements to be sorted ?
one of the simplest sorting algorithms is the insertion sort. Insertionsort consist of N-1 passes .
For pass P=1 through N-1 , insertion sort ensures that the elements in positions 0 through P-1
are in sorted order .It makes use of the fact that elements in position 0
through P-1 are already known to be in sorted order .
6 Write the function in C for insertion sort ?
void insertionsort(elementtype A[ ] , int N)
{
int j, p; elementtype tmp;
for(p=1 ; p <N ;p++ )
{
tmp = a[ p] ;
for ( j=p ; j>0 && a [ j -1 ] >tmp ;j--) a [ j ]=a [j-1 ] ;
a [ j ] = tmp ;
}}
7 Differentiate between merge sort and quick sort? Merge sort quick
sort
1. Divide and conquer strategy Divide and conquer strategy
2. Partition by position Partition by value
8 Mention some methods for choosing the pivot element in quick sort?
1. Choosing first element
2. Generate random number
3. Median of three
52
CS3353_CDS
lOMoARcPSD|47265940
4931-Grace College of engineering
9 What are the three cases that arise during the left to right scanin quick sort?
1. I and j cross each other
2. I and j do not cross each other
3. I and j points the same position
10 What is the need of external sorting?
External sorting is required where the input is too large to fit into memory. So external
sorting Is necessary where the program is toolarge
11 What is sorting?
Sorting is the process of arranging the given items in a logical order. Sorting is an example
where the analysis can be preciselyperformed.
12 What is merge sort?
The merge sort algorithm is a classic divide conquer strategy. Theproblem is divided into
two arrays and merged into single array
13 What does internal sorting mean?
Internal sorting is a process of sorting the data in themain memory
14 What are the various factors to be considered in deciding asorting algorithm?
Factors to be considered in deciding a sorting algorithm are,
1. Programming time
2. Executing time for program
3. Memory or auxiliary space needed for the programsenvironment.
15 Is the heap sort always better than the quick sort?
No, the heap sort does not perform better than the quick sort.
Only when array is nearly sorted to begin with the heap sort algorithm gains an advantage. In
such a case, the quick deterioratesto its worst performance of O (n2).
53
CS3353_CDS
lOMoARcPSD|47265940
4931-Grace College of engineering
16 Name some of the external sorting methods.
Some of the external sorting methods are,
1. Polyphone sorting
2. Oscillation sorting
3. Merge sorting
data with integer keys by grouping keys by the individual digits
which share the same significant position
17 Define searching
Searching refers to determining whether an element is present in a given list of
elements
or not. If the element is present, the search is considered as successful, otherwise it is
considered as an unsuccessful search. The choice of a searching technique is based on the
followingfactors
a. Order of elements in the list i.e., random or sorted
b. Size of the list
18 Mention the types of searching
The types are
● Linear search
● Binary search
19 What is meant by linear search?
Linear search or sequential search is a method for finding aparticular value in a list
that consists of checking every one of its elements, one at a timeand in sequence, until
the desired one is found.
54
CS3353_CDS
lOMoARcPSD|47265940
4931-Grace College of engineering
20 What is binary search?
For binary search, the array should be arranged in ascending or descending order.
In each step, the algorithm compares the search key value with the middle element of the
array. If the key match, then a matching element has been found and its index, or Position, is
returned.
Otherwise, if the search key is less than the middle element, then the algorithm repeats its
action on the sub-array to the left of the middle element or, if the search key is greater, on the
sub-array to
the right.
PART B
1
Explain the sorting algorithms[insertion sort,quick sort,merge sort, heapsort]
2 Explain the searching algorithms[binary search and linear search]
3 Write a C program to sort the elements using quick sort, insertion and merge sort.
4 Write a C program to perform searching operations using linear and binary search.
55
CS3353_CDS
