**UNIT -2 SEARCHING & SORTING TECHNIQUES**

**(2 , 4 & 8 MARKS QUESTIONS)**

**1) Define sorting. Enlist different sorting technique.**

**(Definition – 1 Mark, Technique – 1 Mark (any 4 techniques are expected))**

**Ans:** Sorting: Process by which a collection of items are placed into ascending order or in descending order.

Sorting Techniques:

Bubble Sort

Insertion Sort

Selection Sort

Quick Sort

Merge Sort

Radix Sort

Shell Sort

**2) Define sorting and give its type. (Sorting definition -1Mark, Types-1Mark)**

**Ans:**

Sorting is the operation of arranging data or elements in some given order, numerically or alphabetically.

The sorting is classified into two categories.

**1. Internal Sorting:** In this sorting technique, all the data is retained in main memory only and the data can be accessed randomly.

**2. External Sorting:** In this sorting, the data to be sorted is moved from secondary storage to main memory.

Because the large data may be in secondary storage.

It is more time consuming to move records into different

location.

**3) Write a ‘C’ program to insert an element in an array. (Correct program 4m)**

**Ans:**

void insert(int *arr, int pos, int num)

{

int i;

for(i=max-1;i>=pos; i–)

arr[i]=arr[i-1];

arr[i]=num;

}

**4) Define searching and sorting? Enlist its type?(definition& type 1M each )**

**Ans:**

** Sorting** is the ordering of elements is either ascending or descending order.

Types of sorting:-

1. Internal Sorting 2. External sorting

**Searching:** Searching means to find a particular element from list.

Two types:

1. Linear search 2. Binary Search

**5) Give the principal of bubble sort. (Principal-2 Marks)**

**Ans:**

The algorithm in bubble sort involves two steps,

executed over & over until data is sorted.

1. Compares two adjacent items

2. If necessary, swap (exchange) them

Sorting begins with 0th elements & it compares with 1st element in list.

If 1st element is less than 0th element then interchange takes place.

Like this all elements are compared with next element & interchanged if

required.

At end of 1st pass largest element is placed at last position.

In 2nd pass again comparisons starts with 0th element & 2nd largest

element is placed at second last position.

This process continues till list is in sorted order.

**6) Write a program to arrange 10 elements in an ascending order. (4 marks) ****(Any sorting logic can be consider to arrange 10 elements in ascending order.)**

**OR**

**6) WAP to implement bubble sort. (Complete program 4 marks) ****(Note: program can be written differently depending on the same logic. **

**(Given solution is only code for separate function. Same logic from the code can**

**be used in single program without function)**

**Ans:**

Example bubble sort logic:

void main( ) // or use **bsort(int a[],int n)**

{

int i, j, temp;

printf(“\n\n BUBBLE SORT”);

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

{

for(j=0;j<10-i;j++)

{

if (a[j]>a[j+1])

{

temp=a[j];

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

a[j+1]=temp;

}

}

}

}

**7) Write a program for sorting the ****array of 10 elements using the Bubble ****sort method.((Any Correct logic shall be**

**considered) for correct logic – 4 Marks)**

**Ans:**

#include<stdio.h>

#include<conio.h>

void bubble_sort(int[ ]);

void main()

{

int arr[30], num, i;

printf(“\nEnter 10 array elements

:”);

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

scanf(“%d”, &arr[i]);

bubble_sort(arr);

getch();

}

void bubble_sort(int arr[])

{

int i, j, k, temp;

printf(“\nUnsorted Data:”);

for (k = 0; k < 10; k++)

{

printf(“%d”, iarr[k]);

}

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

{

for (j = 0; j < 10 – 1; j++)

{

if (arr[j] >arr[j + 1])

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

printf(“\nAfter pass %d : “, i);

for (k = 0; k < 10; k++)

{

printf(“%5d”, arr[k]);

}

}

}

**8) Write a ‘C’ program for the selection sort. (Program-2 Mark,Logic -2Mark, any relevant logic shall be considered)**

**Ans:**

#include <stdio.h>

#include<conio.h>

int main ( )

{

int array[100],n, i, j, temp, pos;

printf(“Enter the number of

elements to be sorted: “);

scanf(“%d”, &n);

printf(“enter the elements\n”);

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

{

scanf(“%d”, &array[i]);

}

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

{

pos=i;

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

{

if(array[j]<array[pos])

pos=j;

}

temp=array[i];

array[i]=array[pos];

array[pos]=temp;

}

printf(“The Sorted List Is “);

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

printf(“%d “,array[i]);

getch();

}

**[Note: program can be written ****differently depending on the same ****logic]**

**9) Sort the number in ascending order using selection sort**

**A={ 42, 23, 74, 11, 65}. (two methods-any 1 can be considered-4M)**

**Ans:**

42 23 74 11 65

• Select position 0 and element a[0]
• Consider a[0]=min

• From remaining array (a[1] to a[4]), find out the smallest element.

• If the smallest element is less then min, then perform exchange, (Smallest

element with min).

**Pass 1** min = a[0] = 42

smallest element = 11 as smallest element < min, perform exchange.

**Output of Pass 1**

11 23 74 42 65

Element at 0th position is at proper position.

**Pass 2** min = a[1] = 23

smallest element = 23 as smallest element = min, no exchange.

**Output of Pass 2**

11 23 74 42 65

**Pass 3** min = a[2] = 74

smallest element = 42 as smallest element < min, perform exchange.

**Output of Pass 3**

11 23 42 74 65

**Pass 4** min=a[3] = 74

smallest element = 65 as smallest element < min, perform exchange.

**Output of Pass4**

11 23 42 65 74

Array is sorted using selection sort technique.th final sorted array is

11 23 42 65 74.

**OR**

**10) Describe insertion sort algorithm and give steps of insertion sort for sorting the following list in ascending order. List: 2, 15, 42,26,39,92, 20 also find total number of comparison made.(Algorithm description – 3Marks, Problem solving – 4 Marks, no of comparison -1 Mark) [Note: Appropriate steps describing procedure for sorting shall be considered.]**

**Ans:**

**Insertion Sort**

In insertion sort sorting takes place by inserting a particular element at the

appropriate position

Given List:

2,15,42,26,39,92,20

**Algorithm**

**Step1:** start

**Step2:** First iteration 1st element is compared with 0th element if it is smaller it is inserted in the 0th Place of sorted array.

**Step3:** Compare the remaining elements one by one and place all elements in proper position using shift insert function

**Step4:** Stop

Total No of comparison is 21

**11) Describe merge sort algorithm with an example and state it’s time complexity. (Merge sort Explanation – 1 Mark, Example – 2 Marks, Complexity – 1 Mark)**

**Ans:**

**Method 1:**

In this method two sorted arrays are merged together in a single array. Both the arrays should be in sorted order.

First element from both the array is compared & smaller element is placed inside 3rd array, then 1st element from either of the 2nd array is compared with 2nd element of another array again smaller element is placed in 3rd array.

This process continues till all elements from both the arrays are placed in 3rd array.

**Example:**

array1 array 2

10 1 9 11 46 20 15 0 7 2 2

Both arrays should be in sorted order.

**→ Iteration 1:**

(1) 9 10 11 46 (0) 2 15 20 72

array 3 : 0

**→ Iteration 2:**

(1) 9 10 11 46 0(2) 15 20 72

array 3 :0 1

**→ Iteration 3:**

1(9) 10 11 46 0(2) 15 20 72

array 3: 01 2

**→ Iteration 4:**

1 (9) 10 11 46 0 2 (15) 20 72

array 3: 0 1 2 9

**→ Iteration 5:**

1 9 (10) 11 46 0 2 (15) 20 72

array 3: 0 1 2 9 10

**→ Iteration 6:**

1 9 10 (11) 46 0 2 (15) 20 72

array 3: 0 1 2 9 10 11

**→ Iteration 7:**

1 9 10 11 (46) 0 2 (15) 20 72

array 3: 0 1 2 9 10 11 15

**→ Iteration 8:**

1 9 10 11 (46) 0 2 15 (20) 72

array3: 0 1 2 9 10 11 15 20

**→ Iteration 9:**

1 9 10 11 (46) 0 2 15 20 (72)

array 3: 0 1 2 9 10 11 15 20 46

**→ Iteration 10:**

1 9 10 11 46 0 2 15 20 (72)

Sorted Array

array3: 0 1 2 9 10 11 15 20 46 72

**OR**

**Method 2: Two way merge sort.**

All the elements from the input array are grouped together sorted in order & merged together. Again groups merged, sort & again same procedure is followed till all elements are placed in one single group.

**Example:**

Merge sort | Best-0(n log n) | Average-0(n log n) | Worst-0(n log n) |

**12) Explain merge sort for 6 numbers. (4 marks) (For any numbers)**

**Ans:**

**13) Describe the working of principle of radix sort?**

**(2 marks-Explain/algorithm & 2 marks on example)**

**Ans: **

**Algorithm:**

1. Arrange 10 buckets for numbers or 26 buckets for alphabets.

2. Place each number in respective bucket depending on the position of digit in

the number.

3. Rearrange numbers or alphabets from all buckets into an array.

4. Perform above steps 2 &3 till all elements are placed in sorted order.

**The number of passes will depend on the length of the number having ****maximum digits.**

Suppose we want to sort the following set of three digits numbers:

NUMBER | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|

345 | 345 | |||||||||

654 | 654 | |||||||||

924 | 924 | |||||||||

123 | 123 | |||||||||

567 | 567 | |||||||||

472 | 472 | |||||||||

555 | 555 | |||||||||

808 | 808 | |||||||||

911 | 911 |

NUMBER | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|

345 | 345 | 345 | ||||||||

654 | 654 | |||||||||

924 | 924 | |||||||||

123 | 123 | |||||||||

567 | 567 | |||||||||

472 | 472 | |||||||||

555 | 555 | |||||||||

808 | 808 | |||||||||

911 | 911 |

NUMBER | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|

345 | 345 | |||||||||

654 | 654 | |||||||||

924 | 924 | |||||||||

123 | 123 | |||||||||

567 | 567 | |||||||||

472 | 472 | |||||||||

555 | 555 | |||||||||

808 | 808 | |||||||||

911 | 911 |

**Sorted array:123, 345, 472,555, 567, 654, 808, 911, 924.**

**14) Sort the given no. in ascending order using radix sort.**

**Numbers: 348, 14, 614, 5381, 47 (Each pass- 1 Mark)**

**Ans: 348, 14,614,5381,47**

**Pass 1:** Numbers are sorted on least significant digit. Numbers with the same least significant digit are sorted in the same bucket

**15) Differentiate between the Radix sort and Shell sort methods. ****(Any 2 points of Comparison – 1 Mark each)**

**Ans:**

Radix Sort | Shell Sort |
---|---|

1)Sorting is based with integer keys by grouping keys by the individual digits which share the same significant position and value. | 1) Shell sort is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange or sorting by insertion. |

2) Position wise sorting is done | 2) Floor wise sorting is done. |

3)This algorithm is stable in nature | 3) This algorithm is not stable as its iterations are depended on floor value |

4) Its complexity is O(n) | 4) Its complexity is O( nlog2n) |

5)This is Non-comparison sort as values gets placed in specific position in each iteration> |
5) This is comparison sort algorithm as value get compared with all elements within group |

**16) Differentiate between merge sort and quick sort any two points. ****(Any 2 relevant points can be consider 1 MARK each )**

** Ans:**

POINTS |
MERGE SORT |
QUICK SORT |
---|---|---|

Complexity | O(n log n) | O(n2) |

Working Principle | Merge sort divides unsorted list, sort them in group and then combines them in single array. |
Quick sort requires pivot element selection for sorting. Placing pivot element at its final position divides the list into parts. |

**17) Explain shell sort with an example.[4m explanation & 4m example]**

** Ans:**

1) Shell sort is a generalization of insertion sort

2) Shell sort is considered an improvement over insertion sort.

3) In shell sort the elements are sorted in multiple passes and in each pass, data are taken with smaller and smaller gap sizes.

4) Last step of shell sort is a plain insertion sort. But by the time we reach the last step, the elements are already ‘almost sorted’ and hence it provides good performance.

**The procedure of shell sort is as follows:**

1) In the first Iteration, the elements are splitted with a gap of say 5,3 etc, and are sublisted.

2) The sublist obtained after splitting is again sorted

3) The sorted sublist is recombined

4) The sorted list, in the second iteration, is again sublised with a gap (here it is 3)

5) Repeat through step 2 and 3

6) After getting list finally apply insertion sort if required.

**Example:**

**Sort the following numbers using shell sort.**

** 9,1,4,6,3,5,7,11,14,10,12,0,2,8**

**Ans: Pass 1:** Given number are first sorted at distance 5 from each other.

**Pass 2:** The above sorted list is recombined and again subdivided with distance 3

**18) Write an algorithm for quick sort. (4 marks) (any other relevant steps shall be considered)**

** Ans:**

**Step 1:** Use two index variables i & j with initial values of 1st index position & n-1 index position respectively.

**Step 2:** Compare ith index with pivot element till it finds greater number than pivot element. Increment ith by 1 if ith element is less than pivot element

**Step 3:** jth element is compared with pivot element till it finds a number less than pivot element Decrement jth by 1 if jth element is greater than pivot element.

**Step 4:** After finding elements greater than & less than pivot elements

interchange both the elements.

**Step 5:** After interchange again increment & decrement current position of i & j,

& compare each element with pivot element.

**Step 6:** once all elements are compared with pivot element fix the final position

of pivot element in the list.

**Step 7:** Divide the total array into 2 parts without including fixed position

element.

**Step 8:** Each part then should be sorted with the same procedure as mentioned

above till you get a sorted array.

**19) Explain the linear search algorithm. Also give its limitations. ****(Algorithm-1 Mark, Explanation-2 Marks, Limitation-1Mark; any related algorithm can be considered)**

** Ans:**

Linear search is the easiest search technique in which each element is scanned in a sequential manner to locate the desire element.

In this method, Search begins with the first available record and proceeds to the next available record until we find the target key or conclude that it is not found.

Linear search is also called as “sequential search”.

**Example:**Consider an array with 5 elements

3 | 21 | 11 | 91 | 19 |

A[0] | A[1] | A[2] | A[3] | A[4] |

We are searching for element 91. To search 91 the item 91 is compared with

element at A[0] then A[1] and so on.

Until we find the target value or reach to the end of array.

When item is found it displays the location of an item else displays item not

found.

Algorithm:

1. Start

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

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

4. Set i=0, flag=0

5. Compare A[i] with target

if (A[i] is a target)

Set flag=1 go to step 7

Else

Move to next data element

i= i+1;

6. If (i<=n) go to step 5

7. If(flag=1) then

Return i as position of target

located

Else

Report as target not found.

8. Stop.

Limitation: Highly inefficient for large data

**20) WAP to implement linear search for 10 elements in an array.**

** (Correct program 4 M) (Any other relevant logic can be considered.)**

** Ans:**

# include <stdio.h>

# include <conio.h>

void main ( )

{

int a [10] = {10, 20, 30, 40, 50,60,70,80,90,100};

int num, i ;

printf (“Enter element to be searched”);

scanf (“%d”, &num);

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

{

if (a[i] = = num)

{

Break;

}

}

if (i = = 10)

printf (“Number not found”);

else

printf (“Number found at position %d”, i);

}

2. Write an algorithm to implement binary search.(Algorithm Four marks)

Ans:

1. Binary search algorithm locates the position of an element in a sorted array.

2. Binary search works by comparing an input value to the middle element of the

array.

3. The comparison determines whether the element equals the input, less than

the input or greater.

4. When the element being compared to equals the input the search stops and

typically returns the position of the element.

5. If the element is not equal to the input then a comparison is made to determine

whether the input is less than or greater than the element.

6. Depending on which it is the algorithm then starts over but only searching the

top or bottom of the array’s elements.

**21) Describe Binary search with an example. (Explanation – 2 Marks, Example – 2 Marks)**

** Ans:**

**Binary search:**

Binary search can be performed only on sorted array.

In this method first calculate mid position in an array and compare the mid

position element with the search element.

If a match is found the complete the search otherwise divide the input list into 2

parts.

First part contains all the numbers less than mid elements and 2nd part contains

all the numbers greater than mid element.

To calculate mid element perform (lower + upper) / 2.

The binary search performs the comparison till the element is found or division

of list gives one element.

**22) Find the position of element 29 using binary search method in an array ‘A’ given below: A= {11, 5, 21, 3, 29, 17, 2, 43}**

** Write a ‘C’ program for binary search. (Solution-4 Marks Program-4 Marks)**

** Ans:**

A= {11, 5, 21, 3, 29, 17, 2, 43}

Pre-condition for Binary search is array elements must be sorted in

ascending order.

In given example array elements are not sorted.

Applying Bubble sort we sort the elements of array.

Sorted array A= {2, 3, 5, 11, 17, 21, 29, 43}

i. Low=0 high=7 k=29

Mid= (0+7)/2 = 3

A[mid] =a [3] =11

29>11

k>a [mid]
ii. Low=mid+1 High=7

Mid= (4+7)/2=5

A[mid] =a [5] =21

29>21

k>a [mid]
iii. Low=mid+1

Mid= (6+7)/2=6

A[mid] =a [6] =29

A[mid] =k

Therefore key element is found at 6th position, no. of comparison required = 3.

Search is successful

‘C’ program for Binary Search.

#include<stdio.h>

#include<conio.h>

void main( )

{

int a[12];

int item, n, mid, i, lower, upper, flag=0, count=0;

char ch=’y';

clrscr( );

printf(“\n ***** BINARY SEARCH METHOD *****”);

printf(“\n Enter The Number Of Elements You Want In The Array: 1 To 12 \n “);

scanf(“%d”, &n);

printf(“Enter the elements of the array\n”);

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

{

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

}

do

{

printf(“\nEnter The Key Element To Be Searched:”);

scanf(“%d”, &item);

lower=0;

upper=(n-1);

flag=0;

count=0;

while(lower<=upper)

{

mid=(lower+upper)/2;

count++;

if(item==a[mid])

{

printf(“\n The element %d is found at: %d”, item, mid);

flag=1;

break;

}

else

{

if(item>a[mid])

{

lower=(mid+1);

}

else

{

upper=(mid-1);

}

}

}

if(flag!=1)

{

printf(“\n The element is not found!”);

}

printf(“\n The no of comparisons:%d”, count);

printf(“\n Do You Want To Continue : (Yes/No)”);

fflush(stdin);

scanf(“%c”, &ch);

}

while(ch == ‘y’ || ch == ‘Y’);

getch();

}

**23) Find the position of element 88 using binary search method in an array given below: A={77,33,44,11,88,22,66,55} Write a ‘c’ program for binary search. (4 marks for problem & 4 marks for code)**

** Ans:**

Precondition of binary search is array should be sorted.

Sorted array A: 11 22 33 44 55 66 77 88 Key:=88

**Pass 1:** low=0, high=7 & mid=3

Compare key with A[mid] i.e 44

88>44,

so low=4, high=7 & mid=5

**Pass 2:** low=4, high=7 & mid=5

Compare key with A[mid] i.e 66

88>66

So low=6,high=7 & mid=6

**Pass 3:** low=6,high=7 & mid=6

Compare key with A[mid] i.e.77

88>77,

so low=7,high=7,mid=7

**Pass 4:** low=7,high=7,mid=7

Compare key with A[mid] i.e 88

88=88, search is successful & position is mid 88 found at position 7

#define max binary(int a[], int key, int n)

{

int i ,low, high, mid, item=0,flag=1;

low=0;

high=n-1;

for(mid=(low+high)/2;low<=high; mid=(low+high)/2 )

{

item++;

if(a[mid]==key)

{

flag=0;

break; //SEARCH IS SUCCESSFUL ,BREAK THE LOOP

}

if(a[mid]<key)

low=mid+1;

else

high=mid-1;

}

if(flag==0)

printf(“\n %d IS FOUNTD AT LOCATION %d WITH %d INTERATION “,key,

mid, item);

else

printf(“\n %d IS NOT FOUND “,key);

}

IT IS VERY IMPORTANT TO STUDENT …………….. I am very happy to my teachers provide E-learning.”””

Thanks Vaishnvee we are adding more contents with detail explanation. Keep Visiting..