DSU Chapter 2: Searching and Sorting

Unit – 2
Searching and Sorting [12]
Course Outcome: Perform basic operation on array.
Syllabus:
1. Searching an item in a dataset using following methods:
i. Linear Search
ii. Binary Search
2. Sorting of data set in an order using following methods:
i. Bubble Sort
ii. Selection Sort
iii. Insertion Sort
iv. Quick Sort
v. Radix Sort

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

SEARCHING
 We often spend time in searching for the desired item. If the data is kept properly in sorted order
then searching becomes very easy and efficient.
 Searching is an operation which finds the place of a given element in the list. The search is said to
be successful or unsuccessful depending upon whether the element is found or not found.

Explain Linear Search with example.

 This is the simplest method of searching. In this method, the element to be found is
searched sequentially in the list. This method can be used on sorted or unsorted list.
 Linear search is also called as sequential search. Linear search is the easiest search
techniquein which each element is scanned in a sequential manner to locate the desire
element.
 Linear search is a method for finding a particular value in a list. In this searching
technique you needto check every element one by one until desired element fou
___________________________________________________________________________

Example of linear search:

Array = [3 21 11 19 91 4 80], Key element to search = 91

Key Element = 91

Element Found at Position 4

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

_____________________________________________________________________________________________

State algorithm for Linear search.

Step 1: Start

Step 2: Accept n values from user i.e. array elements.

Step 3: Accept element to be searched from user i.e. target.

Step 4: Set i=0, flag=0

Step 5: Compare A[i] with target If(A[i] is a target)

Step 6: Set flag=1 go to step 7 Else Move to next data element i= i+1;

Step 7: If (i<=n) go to step 5

Step 8: If(flag=1) then Return i as position of target located Else Report as target not
found.

Step 9: Stop.
_____________________________________________________________________________
Program for Linear Search

Program for Linear Search

#include<stdio.h>
#include<conio.h>
void main()
{
int list[10]={12,3,11,13,48,22,17,2,74,4};
int i, no;
printf(“ Enter number to search\n”) :
scanf(“%d”,&no);
for(i=0; i<=9; i++)
{
if(list[i] == no)
break;
}
if (i==10)
printf(“Number is not present in the array”);
else

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

printf(“The number is at position %d in the array”,i);

getch();
}
__________________________________________________________________________________________________

Advantage of linear search:

 Easy to implement
 Does not required list to be sorted.
 It does not require any additional data structure.

Disadvantage of linear search:

 Inefficient for large size lists.

Time Complexity:
 In Average case the comparisons required to find the location of element is approximately
equal to half of the number of elements in the array. In worst case the entire array is search.
So it requires N comparisons. Thus the time complexity in worst case is O(N).
___________________________________________________________________________________________

Explain Binary Search with example.

 Binary search technique is very fast and efficient. It requires the list of elements to be in
sorted order.
 In this method, to search an element we compare it with the element present at the centre
of the list. If it matches then the search is successful, otherwise the list is divided into two
halves – one from the 0th element to the center element (first half) and another from the
center element to the last element (second half).
 As a result all the elements in first half are smaller than centre element whereas all the
elements in second half are greater than the center element.
 Check whether target element is greater or smaller than center element. If element is smaller
then center element searching is done in first half, otherwise it is done on second half and
process is continued.

__________________________________________________________________________________________________

Example of binary search:1

Array = [2 4 7 9 10 11 15 20 46 72], Key element to search = 15

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

__________________________________________________________________________________________________

Example 2:
To search element = 3
0 1 2 3 4 5 6 7 8 9
1 2 3 10 11 13 16 21 46 73
L M U
M= (L + U)/2 = (0+9)/2 = 4
i.e 11 ! = 3
11>3 shift U to M-1

0 1 2 3 4 5 6 7 8 9
1 2 3 10 11 13 16 21 46 73
L M U

M= (L + U)/2 = (0+3)/2 = 1
i.e 2 ! = 3
2< 3 shift L to M+1

0 1 2 3 4 5 6 7 8 9
1 2 3 10 11 13 16 21 46 73
L,M U
M= (L + U)/2 = (2+3)/2 = 2
i.e 3 = 3
Element is found at location 2
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

__________________________________________________________________________________________________

Advantage of binary search:

 It requires lesser number of iterations.
 It is a lot faster than linear search.

Disadvantage of binary search:

 it requires the list to be sorted.
 Little difficult to implement.

Time Complexity = O(log2 n)

__________________________________________________________________________________________________

State algorithm for binary search.

Step 1: Start
Step 2: Set i = 0, j = size, k = 0
Step 3: Repeat Steps 4-9 while i <= j
Step 4: Set k = (i + j)/2
Step 5: If arr[k] = num goto Step 6 else goto Step 7
Step 6: return k and goto Step 11
Step 7: If array[k] < num goto Step 8 else goto Step 9
Step 8: i = k + 1
Step 9: j = k - 1
Step 10: Return NULL and goto Step 11
Step 11: Stop

__________________________________________________________________________________________________

Program of Binary Search

#include<stdio.h>

#include<conio.h>

void main()

int e,n,i,a[10],mid=0,beg,end,flag=0;

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
clrscr();

printf("Enter n Element");

scanf("%d",&n);

printf("Enter Array Element");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

printf("Enter Key Element");

scanf("%d",&e);

beg=0;

end=n-1;

while(beg<end)

mid=(beg+end)/2;

if(e==a[mid])

printf("No is present");

flag=flag+1;

break;

else if(e<a[mid])

end=mid-1;

}
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
else if(e>a[mid])

beg=mid+1;

if(flag==0)

printf("No is absent");

getch();

\\OUTPUT\\

Enter n Element:10

Enter Array Element:1 2 3 4 5 6 7 8 9 10

Enter Key Element: 5

No is present

__________________________________________________________________________________________________

Differentiate between linear and binary search.

Parameters Linear Search Binary Search

Array must be in sorted
1. Prerequisite No required
order.

2. Lines of code Less More

3. Algorithm type Iterative Divide and conquer

4. Usefulness Easy to use Tricky algorithm

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
Difficult to insert to
5. Inserting operation Easy to insert
maintain sorted order.

6. Time complexity O (N) O (log 2 N)

7. Best case First time Centre time

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

Sorting Methods
Sorting refers to the operation of arranging a set of data in some given order. A collection of records is
called a list, where each record contains one or more fields. The field which contains unique value for each
record is known as the key field. For example, the record of students contains three fields (rollno, name,
address) in which rollno is a unique called a key.

The methods of sorting can be divided into two categories.

 Internal Sorting
 External Sorting
Internal Sorting : If all the data that is to be sorted can be adjusted at a time in main memory, then internal
sorting methods are used.
External Sorting : When the data to be sorted cannot be accommodated in the memory at the same time
and some has to be kept in auxiliary memory (hard disk, floppy, tape etc.) then external sorting methods
are used.

__________________________________________________________________________________________________

Explain bubble sort with example.

 Bubble sort is one of the oldest and simplest of sorting techniques. In Bubble sort each
elementof the array is compared with its adjacent element.

 It focuses on bringing the largest element to the end of the list with each successive
pass. The algorithm processes the list in passes. A list with n elements requires n-1
passes for sorting.
The algorithm in bubble sort involves two steps, executed over and over until the data is sorted.
1. Compare two adjacent items.
2. If necessary, swap (exchange) them.
 In this sorting method, to arrange elements in ascending order, we begin with 0 th element and
compare it with the 1st element.
 If it is found to be greater than 1st element then they are interchanged. Compare 1st element
with 2nd element and so on. In this way all the elements are compared with their next element
and are interchanged if required.
 On completing the first iteration, the largest element gets placed at the last position. Similarly
in the second iteration second largest element gets placed at the second last position and so on.
As a result after all the iterations the last becomes a sorted list.

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
__________________________________________________________________________________________________

Example 1:

1st Iteration
23 15 29 11 1

Exchange 15 < 23
15 23 29 11 1
No Exchange

15 23 29 11 1

Exchange 11 < 29
15 23 11 29 1
Exchange 1 < 29

15 23 11 1 29

2nd Iteration
15 23 11 1 29
No Exchange
15 23 11 1 29
Exchange 11 < 23

15 11 23 1 29
Exchange 1 < 23

15 11 1 23 29
No Exchange

15 11 1 23 29

3rd Iteration

15 11 1 23 29
Exchange 11 < 15

11 15 1 23 29
Exchange 1 < 15

11 1 15 23 29
No Exchange

11 1 15 23 29
No Exchange

11 1 15 23 29

4th Iteration

11 1 15 23 29
Exchange 1 < 11

1 11 15 23 29

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
Array is Sorted

__________________________________________________________________________________________________
Advantage of bubble sort
 It is easy to understand and implement.
 Better efficiency.

Disadvantage of bubble sort

 Not well suited for large size lists.
 Slow in execution.

Efficiency of bubble sort: O (n2)

__________________________________________________________________________________________________

State algorithm for bubble sort.

Step 1: Start
Step 2: Set i = size, j = 0 and temp = 0
Step 3: Repeat Steps 4-9 while i > 1
Step 4: Set j = 0
Step 5: Repeat Steps 6-8 while j < i-1
Step 6: if arr[j] > arr[j+1] goto Step 7 else goto Step 8
Step 7: Swap the elements stored at arr[j] and arr[j+1] by performing the
following steps
Set temp = a[j+1]
Set arr[j+1] = arr[j]
Set a[j]=temp
Step 8: Set j = j + 1
Step 9: Set i = i - 1
Step 10: Stop.

__________________________________________________________________________________________________

Program : BUBBLE SORT

#include<stdio.h>

#include<conio.h>

void main()

int a[5],i,j,temp;

clrscr();
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
printf("Enter Elements in array");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

for(i=0;i<5;i++)
{
for(j=0;j<4;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}

printf("The sorted array is");

for(i=0;i<5;i++)

printf("%d", a[i]);

getch();

\\OUTPUT\\

Enter Element in Array: 2 4 1 3 5

The Sorted Array is: 1 2 3 4 5

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
__________________________________________________________________________________________________

Explain selection sort with example.

The selection sort is the easiest method of sorting. In this sort the data is arranged in ascending order. The
0th element is compared with all other elements, if the 0th element is found to be greater than the compared
element then they are interchanged. In this way after the first iteration the smallest element is placed at 0th
position. The procedure is repeated for 1st element and so on.

Example of selection sort: Array [4 9 5 1 0]

Pass 1: In pass 1, 0th element is compared with all other elements. (ie. 1st, 2nd, 3rd, and 4th)

Pass 2: In pass2, 1st element is compared with all other elements. (ie. 2nd, 3rd, and 4th)

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

Pass 3: In pass 3, 2nd element is compared

with all other elements. (ie. 3rd, and 4th)

Pass 4: In pass 4, 3rd element is compared with all other elements. (ie. 4th)

__________________________________________________________________________________________________
Advantage of selection sort
 Simple and easy to understand.
 Does not require additional memory space.

Disadvantage of selection sort

 Not well suited for large size lists.

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
 Does not leverage the presence of any existing sort pattern.

Efficiency of selection sort: O (n2)

__________________________________________________________________________________________________

State algorithm for selection sort.

Step 1: Start
Step 2: Set i = 0, loc = 0 and temp = 0
Step 3: Repeat Steps 4-6 while i < size
Step 4: Set loc = Min(arr, i, size)
Step 5: Swap the elements stored at arr[i] and a[loc] by performing the
following steps
Set temp = a[loc]
Set a[loc] = a[i]
Set a[i]=temp
Step 6: Set i = i +1
Step 8: Stop

__________________________________________________________________________________________________

Program: SELECTION SORT

#include<stdio.h>

#include<conio.h>

void main()

int i,j,temp,a[5];

clrscr();

printf("Enter array element:");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

for(i=0;i<4;i++)

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
{

for(j=i+1;j<5;j++)

if(a[i]>a[j])

temp=a[i];

a[i]=a[j];

a[j]=temp;

printf("Sorted Array is:");

for(i=0;i<5;i++)

printf("%d",a[i]);

getch();

\\OUTPUT\\

Enter array element: 1 3 4 5 2

Sorted Array is: 1 2 3 4 5

__________________________________________________________________________________________________

Explain insertion sort with example.

 The insertion sort is substantially better than bubble sort. It is about twice as fast as the bubble sort.
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
It is also not too complex, although it is slightly more involved than the bubble sort. It is often used
as the final stage of more sophisticated sorts, such as quick sort.
 Insertion sort is performed by inserting a particular element at the appropriate position. In insertion
sort, the first iteration starts with comparison of 1st element with the 0th element.
 In the second iteration, 2nd element is compared with the 0th and 1st element. In general in every
iteration, an element is compared with all elements.
 If at same point it is found that the element can be inserted at a position then space is created for it
by shifting the other elements one position to the right and inserting the element at the suitable
position. This procedure is repeated for all the elements in the array.
__________________________________________________________________________________________________
Example of insertion sort: Array [ 15 9 30 10 1]

Pass 1: 1st element is compared with all previous elements ( ie. 0th)

Pass2: 2nd element is compared with all previous elements (ie, 0th and 1st )

Pass3: 3rd element is compared with all previous elements (ie, 0th, 1st and 2nd )

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

Pass4: 4th element is compared with all previous elements (ie, 0th, 1st , 2nd and 3rd )

________________________________________________________________________________________________

Algorithm for insertion sort

1. First iteration the 1st element 15 compared with 0th element 09. since 15>09 move 15 to the right
and insert 9 in its correct position.
2. Second iteration the 2nd element 30 is compared with 0th element 15 and 1st element 9. Since 30>
15 and 9 insertion does not take place.
3. Third iteration the 3rd element 10 compared with 30, since 30>10 move 30 to right and compare
10 with 15. Again 15>10 move 15 to right and compare 9 with 10, As 9<10 nothing is done.
4. In fourth iteration the 4th element is compared with remaining all elements since 30 >1 move 30
to the right. Likewise 15 10 and 9 is also greater than 1, so shift all element with towards right by
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
one position and insert 1 at appropriate position. The array now becomes a sorted array.
__________________________________________________________________________________________________

Advantage of insertion sort

 Simple and easy to implement.

 Perform well for small lists.

Disadvantage of insertion sort

 Not well suited for large size lists.

 Requires large number of elements to be shifted.

Efficiency of insertion sort: O (n2)

__________________________________________________________________________________________________

State algorithm for insertion sort.

Step 1: Start
Step 2: Set i = 1, j = 0 and temp = 0
Step 3: Repeat Steps 4-12 while i < size
Step 4: Set temp = arr[i]
Step 5: Set j = i-1
Step 6: Repeat Steps 7-10 while j>=0
Step 7: if arr[j] > temp goto Step 8 else goto Step 9
Step 8: Set arr[j+1] = arr[j]
Step 9: Branch out and go to Step 11
Step 10: Set j = j-1
Step 11: Set arr[j+1] = temp
Step 12: Set i = i + 1
Step 13: Stop

__________________________________________________________________________________________________

Program: INSERTION SORT

#include<stdio.h>

#include<conio.h>

void main()

int a[5],i,j,k,temp;

clrscr();

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
printf("Enter Array Elements:");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

for(i=1;i<5;i++)

temp=a[i];

j=i-1;

while((j>=0)&&(a[j]>temp))

a[j+1]=a[j];

j=j-1;

a[j+1]=temp;

printf("The Sorted Array is");

for(i=0;i<5;i++)

printf("%d",a[i]);

getch();

\\OUTPUT\\

Enter Array Elements:2 1 3 4 5

The Sorted Array is12345

__________________________________________________________________________________________________

Explain quick sort with example.

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
 Quick sort is very popular sorting method. It was introduced by Haore in 1962. It is very
important method of internal sorting.
 According to this algorithm, it is faster and easier to sort two small arrays than one large
one. The strategy that quick sort follows is of divide and conquer.
 In this approach, numbers are divided and again subdivided and division goes on until it is
not possible to divide them further.
 The procedure it follows is of recursion. It is also known as Partition Exchange Sort. I
 n the below figure, * indicates pivot element and @ indicates the element whose position is
finalized.
 Quick sort algorithm contains mainly three parts;

Elements less than the Pivot element

Pivot element
Elements greater than the pivot element

__________________________________________________________________________________________________
Algorithm for quick sort

1. In 1st iteration, the 0th element 10 is placed at its final position and the array is divided. Two index
variables a and b are taken to divide the array. The indexes are initialized in a way such that a refers
to 1st element 1 and b refers to (n  1)th element 2.
2. A search an element that is greater than value of 0th location. So a is incremented by one till the
value stored at a is greater than 0th element, it is incremented till 11, as 11 is greater than 10.
3. Similarly b search an element that is smaller than 0th element. So b is decremented by one till the
value stored at b is smaller than the value at 0th location. In our case, b is not decremented because
2 is less than 10.
4. When these elements are found, they are interchanged. Again from the current positions, a and b
are incremented and decremented respectively and exchanges are made appropriately if desired.
5. The process ends whenever the index pointers meet. In our case they are crossed at the value 0 and
20 for the indexes a and b respectively. Finally the 0th element 10 is interchanged with the value of
index b i.e. 0. The position b is now the final position of the pivot element 10.
6. As a result the whole array is divided into two parts where all the elements before 10 are less than
10 and all the element after 10 are greater than 10.
The same procedure is applied for two sub arrays. As a result at the end when all sub arrays are left
with one element, the original array becomes sorted.
__________________________________________________________________________________________________
Example:
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

10 1 9 11 46 20 15 0 72 2
* a b
Increment a by 1
10 1 9 11 46 20 15 0 72 2
* a b
Increment a by 1
10 1 9 11 46 20 15 0 72 2
* a b
Increment a by 1
Since a>* and b<* Swap a and b

10 1 9 2 46 20 15 0 72 11
* a b

Increment a by 1 and decrement b by 1

10 1 9 2 46 20 15 0 72 11
* a b

Decrement b by 1
10 1 9 2 46 20 15 0 72 11
* a b

Since a>* and b<* Swap a and b

10 1 9 2 0 20 15 46 72 11
* a b

Increment a by 1 and decrement b by 1

10 1 9 2 0 20 15 46 72 11
* a b

Decrement b by 1
10 1 9 2 0 20 15 46 72 11
* a,b

10 1 9 2 0 20 15 46 72 11
* b a

Once a and b crossed swap * and b

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

0 1 9 2 10 20 15 46 72 11
*

Now pivot element ie 10 is placed at its final position and array is divided in two subarray
And apply same procedure for subarrays.
20 15 46 72 11
0 1 9 2 10
* a b * a b

0 1 9 2 20 11 46 72 15
* a b 10 * a b

20 11 46 72 15
0 1 9 2 10 * a b
* a, b

20 11 15 72 46
0 1 9 2 10 * a b
*,b a

20 11 15 72 46
10
* a, b

0 1 9 2
* a b

0 1 9 2 10 20 11 15 72 46
* a, b * a, b

0 1 9 2 10 15 11 20 72 46

0 1 2 9 10 11 15 20 46 72

_______________________________________________________________________________________________

Advantage of quick sort

 Fastest sorting algorithm.

 Does not require any additional memory space.

Disadvantage of quick sort

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
 Not well suited for large size lists.
 Little complex.

Efficiency of quick sort: O (n2)

__________________________________________________________________________________________________

Explain radix sort with example.

 The radix sort is used generally when we intend to sort a large list of names alphabetically. Radix
in this case can be 26, as there are 26 alphabets.
 If we want to arrange a list of names we can classify names into 26 classes, where the first class
consists of those names starting with ‘A’ and second class consists of names starting with ‘B’ and
so on. All this is done in first iteration. In second iteration each class is alphabetized according to
the second letter of the name and so on.
 The radix sort method is used by a card sorter. A card sorter contains 13 receiving pockets labeled
as follows.
9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, R(Reject)
 The radix sort is based on the values of the actual digits in the positional representation ex. The
number 235 in decimal notation is written with a 2 in a hundred’s position, 3 is ten’s position and
5 in the unit’s position.
 The sorter used above uses decimal numbers where the radix is 10 and hence uses only the first 10
pockets of the sorter. To sort element in ascending order, collect element from bucket no. 0 to 9
and to sort element in descending order, collect element from bucket no. 9 to 0 from top to botton.
______________________________________________________________________________________________
Example:

242, 986, 504, 428, 321

First Iteration
Inputs Pockets
0 1 2 3 4 5 6 7 8 9
242 242
986 986
504 504
428 428
321 321

Second Iteration
Inputs Pockets
0 1 2 3 4 5 6 7 8 9
428 428

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
986 986
504 504
242 242
321 321

Third Iteration
Inputs Pockets
0 1 2 3 4 5 6 7 8 9
986 986
242 242
428 428
321 321
504 504

The sorted list as follows

986 504 428 321 242
in example, in first iteration the unit’s digits are stored into pockets and are then collected from pocket 9 to
0. The digits sorted and collected are send as input and second iteration where ten’s digits are sorted and
again collected are send to the third iteration. Where hundred’s digits are sorted and collected. Finally it
gives the sorted list.

__________________________________________________________________________________________________
Algorithms for radix sort
1. In first iteration the elements are picked up and kept in various pockets checking their unit's digit.
2. The cards are collected from pocket 9 to pocket 0 and again they are given as input to the sorter.
3. In second iteration the ten’s digits are sorted.
4. Repeat through step 2.
5. In the third iteration the digits at hundred’s position are sorted.
6. Repeat through step 2.
__________________________________________________________________________________________________

Advantage of radix sort

 Fast when the keys are short i.e. when the range of the array elements is less.
 Used in suffix array construction algorithms.

Disadvantage of radix sort

 Radix Sort is much less flexible than other sorts.

 It takes more space compared to quick sort.

Time complexity : Number of comparisons require for radix sort algorithm in the worst case f(n)=O(n 2)

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
and in best case f(n)=O(n log2 n)
__________________________________________________________________________________________________

Differentiate between insertion sort and selection sort.

Parameters Insertion sort Selection sort

The data is sorted by
The data is sorted by inserting the selecting and placing the
1. Basic
data into an existing sorted file. consecutive elements in
sorted location.
2. Nature Stable Unstable
Elements are known beforehand
3. Process to be Location is previously known
while location to place them is
followed searched. while elements are searched.
4. Best case
O (n) O (n2)
complexity

Differentiate between Bubble sort and Selection sort.

Parameters Bubble sort Selection sort

Largest element is selected
Adjacent element is compared and
1. Basic and swapped with the last
swapped
element
2. Nature Stable Unstable

3. Efficiency Inefficient Improved efficiency

4. Best case
O (n) O (n2)
complexity

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

Method Time Complexity Space Complexity

Radix Sort O(n log n) Additional space only for temporary variables
is required
Bubble Sort Best : O(n) Additional space only for temporary variables
Worst : O(n2) is required
Selection sort O(n2) O(n) total O(1) Auxiliary
Quick Sort Best : O(n log n) Space depends upon number of nested
Worst O(n2) recursive calls or size of the stack
Insertion sort Best : O(n) Only for temporary variables
Worst : O(n2)

MSBTE Questions

Winter 2018
1. Describe working of linear search with example. 4M
2. Find the position of element 29 using binary search method in an array 4M
‘A’ given below. Show each step.
A = {11, 5, 21, 3, 29, 17, 2, 43}
3. Describe working of bubble sort with example. 4M
4. Describe working of selection sort method. Also sort given input list in 4M
ascending order using selection sort input list – 55, 25, 5, 15, 35.

Summer 2019
1. Explain the working of Binary search with an example. 4M
2. Sort the following numbers in ascending order using quick sort. Given 4M
numbers 50, 2, 6, 22, 3, 39, 49, 25, 18, 5
3. Differentiate between binary search and sequential search (linear 4M
search).
4. Sort the following numbers in ascending order using Bubble sort. 4M
Given numbers: 29, 35, 3, 8, 11, 15, 56, 12, 1, 4, 85, 5 & write the
output after each interaction.

Winter 2019
1. Sort the given numbers in ascending order using Radix sort: 348, 14, 4M
641, 3851, 74
2. Draw a binary search tree for the given numbers: 50, 33, 44, 22, 77, 35, 4M
60, 40
3. Implement a ‘C’ program to search a particular data from the given 4M
array using Linear Search.
4. Find the position of element 21 using Binary Search method in Array 4M
‘A’ given below: A = {11, 5, 21, 3, 29, 17, 2, 45}
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
1. Consider an array A = {23, 16, 5, 105, 64, 10} (May 2003)
Apply merge sort algorithm to
(a) Indicate the status of array A at the end of first pass.
(b) Total number of passes required to sort the array.
Sol. :
(a) The status of array A at the end of first pass : 23, 16, 105, 64, 10
(b) The total number of passed required to sort the array is 6.

2. Consider an array A = {23, 16, 5, 105, 64, 10} (Nov. 2003)

Apply ‘Bubble Sort’ technique to
(a) Give the total number of passes required to sort the array A.
(b) Find out the total number of exchanges carried out in the first pass.
Sol. : Pass-1
23 16 16 16 16
16 23 5 5 5
5 5 23 23 23
105 105 105 105 64
64 64 64 64 105
10 10 10 10 10
Pass-2
16 5 5 5
5 16 16 16
23 23 23 23
64 64 64 64
10 10 10 10
105 105 105 105

Pass-3
5 5 5
16 16 16
23 23 23
10 10 10
64 64 64
105 105 105
Pass-4
5 5
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
16 16
10 10
23 23
64 64
105 105
Pass-5
5
10
16
23
64
105
Result : Sorted Array
5
10
16
23
64
105
(a) Total number of passes required to sort the array A is 5.
(b) The total number of exchanges carried out in the first pass are five.

3. Consider the array A={23, 16, 5, 105, 64, 125, 10, 18, 40, 20} (Nov. 2003)
Find the number of comparisons necessary to locate the position of the element fifteen(15) in
the given array or to indicate that element 15 is not present in the array, using Linear Search
Technique.
Sol. : By using linear search technique to search 15 element.
Take first element from array i.e. 23 compare with 15. It is not same that is to be searched. So take
second element i.e. 16, compare with 15. It is not also the same. Like this take one by one element from
array and compare with 15 each and check. The given array does not contain number 15 so the message is
print “Search Not Found” or “Element 15 not present in Array”.

4. Find the position of element 64 using Binary search technique in array A given below : A={
5, 16, 23, 64, 95, 105, 125, 150}
Mention the positions of ‘L’ (Lower Bound), ‘U’ (Upper Bound) and ‘M’ (Middle element)
at the end of each iteration. (Nov. 2003)
Sol. : Given array A={ 5, 16, 23, 64, 95, 105, 125, 150}
Now finding the position of element 64
Let L=1, U=8, M=5
M=(L+U)/2 = (1+8)/2 = 4

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
Here A[M]=95
Since 64 is less than 95 so change U=M-1 = 5-1= 4.
Here A[M]=64
Hence the required position of element 64 is 4.

5. Arrange the data elements in ascending order for array A given below, using Radix Sort
technique.
A={ 1234, 348, 143, 423, 76, 5} Give the following details of the Radix sort algorithm
1. Working and contents of array at the end of each pass.
2. Complexity (for average and worst cases). (Nov. 2003)
Origin Bucket 1st Merge 2nd Merge 3rd Merge 4th Merge

Table Pass Pass Pass Pass

1234 0 143 5 5 5,76 5 5,76,143 5

348,423

348 1 423 423 143 76 1234 76

143 2 1234 423 1234 1234 143 143

423 3 143,423 5 1234 143 348 1234 348

76 4 1234 76 143,348 348 423 348 423

5 5 5 348 76 423 1234

6 76 76

8 348

6. Find the position of element 99 using Linear search method in array given below :
A = {60, 20, 10, 99, 120} (4m, April 2004)
Sol. : Given array A={60, 20, 10, 99, 120}
To find no=99
1. POS=1
If (no==A[0] ) i.e. (99==60)
Position=1
Exit
Else
2. POS=2
If (no==A[1] ) i.e. (99==20)
Position=2
Exit
Else
3. POS=3
If (no==A[2] ) i.e. (99==10)

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
Position=3
Exit
Else
4. POS=4
If (no==A[3] ) i.e. (99==99)
Position=4
Stop
So the position of 99 is 4th element in array.

8. Compare Linear Search (sequential search) and Binary Search techniques.

Sol. :
Linear Search Binary Search

Search time is O(n). Search time is O(log n).

This search is applicable to a table organized While applying binary search, the elements
either as an array or a linked list. must be sorted.

The comparison of items will start from first The array to be searched is divided into two
element to last element. parts using the formula.

This search technique will require more time as This search is much efficient and powerful
compared to binary search. technique.

Any relational operator is used Only ‘=’ relational operator is used

Access is slow Access is faster

Used for single/multidimensional array Used for only single dimensional array

10. Consider the following set of 10 numbers

85, 36, 87, 10, 91, 18, 15, 52, 73, 49
Sort the array using
(A) Insertion Sort (B) Quick Sort
Sol: Using Insertion sort
85 36 87 10 91 18 15 52 73 49
*
36 85 87 10 91 18 15 52 73 49
*
36 85 87 10 91 18 15 52 73 49
*
10 36 85 87 91 18 15 52 73 49
*
10 36 85 87 91 18 15 52 73 49
*
SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
10 18 36 85 87 91 15 52 73 49
*
10 15 18 36 85 87 91 52 73 49
*
10 15 18 36 52 85 87 91 73 49
*
10 15 18 36 52 73 85 87 91 49
*
10 15 18 36 49 52 73 85 87 91

Using Quick sort

* take 85 as a pivot element
85 36 87 10 91 18 15 52 73 49

49 36 87 10 91 18 15 52 73

49 36 10 91 18 15 52 73 87

49 36 73 10 91 18 15 52 87

49 36 73 10 18 15 52 91 87

49 36 73 10 52 18 15 91 87
*
49 36 73 10 52 18 15 85 91 87

ARRAY 1 ARRAY 2
After finding the exact position of pivot element 85, array is divided into two sub-array. Array 1 contains
element less than 85 and array 2 contains element greater than 85. continue the sorting procedure till all
element are to be sorted

11. Differentiate between Internal sort and external sort

Internal Sort External Sort
If all the data that is to be sorted can be adjusted When the data to be sorted cannot be
at a time in main memory, then internal sorting accommodated in the memory at the same time
methods are used. and some has to be kept in auxiliary memory
(hard disk, floppy, tape etc.) then external
sorting methods are used
For internal sort, you need to code a But in case of External sort, there is no need for

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting
program by specifying the sort criteria and that coding the program. Moreover you can change
the program need to be compiled and linked. the sort criteria just by changing the sort
parameters that passed thru the SYSIN card.
Internal sort is not an efficient External sort is more efficient
It is slow process It is a faster process
Its take more time It takes less time
Internal sort gives you data handling flexibility Large amount of space will be required in
and its take less secondary memory external sort
Internal sorting is used for small volumes of External sorting is used for huge volume of
data data
Internal sort is simple External sort is more complicated

12. Find the position of element 64 using Linear search method in array A given below :
A = {23, 16, 5, 105, 64,125} (8m, Dec 2004)
Sol. : Given array A={23, 16, 5, 105, 64, 125}
To find no=64
1. POS=1
If (no==A[0] ) i.e. (64==23)
Position=1
Exit
Else
2. POS=2
If (no==A[1] ) i.e. (64==16)
Position=2
Exit
Else
3. POS=3
If (no==A[2] ) i.e. (64==5)
Position=3
Exit
Else
4. POS=4
If (no==A[3] ) i.e. (64==105)
Position=4
Exit
Else
5. POS=5
If (no==A[4] ) i.e. (64==64)
Position=5
Stop
So the position of 64 is 5th element in array.

SUSHAMA PAWAR
DSU Chapter 2: Searching and Sorting

EXERCISES
1. Compare the performance of selection and insertion sort.
2. For array elements given below, show trace of
(a) Bubble Sort (b) Selection Sort (d) Radix Sort algorithms
5, 22, 17, 35, 38, 28, 40, 42
3. Explain insertion sorting, state its advantages and disadvantages. Write a program to arrange
given ‘N’ numbers in ascending order using insertion sort
A={65, 32, 39, 21, 54, 85, 61, 16, 83, 45} (April 2005-8m)
4. Compare linear search and binary search techniques (minimum 4 points of comparison)
(Nov. 2004 – 4m)
5. Find the position of 46 using linear search method in array A given below
A={ 32, 16, 5, 51, 46, 70} (April. 2005 -8m)
6. Consider an array A={5, 16, 24, 64, 96, 106, 125, 150}. Find the number of comparisons
necessary to locate position of element 96 in the given array using binary search techniques
(April-May 2003 -4m)
7.Write a program in ‘C’ language for selection sort and arrange the given numbers in
ascending order using selection sort. Numbers: 16, 23, 16, 9, 7, 5 (8m, May-08)
8. Explain Binary Search algorithm and also give its advantages (4m, May-08)

SUSHAMA PAWAR