DS Unit 2 Notes

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

sorting

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

list

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:

sorting1
Time complexity:-

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:

mergesort

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

radix

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.

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

shellsort2

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.

binarysearchbinarysearch2

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);
}

2 thoughts on “DS Unit 2 Notes

Leave a Reply

Your email address will not be published. Required fields are marked *