Assignment – Unit 2
Q1. List types of Searching.
Answer:
There are mainly two types of searching:
1. Linear Search
2. Binary Search
Q2) What is Linear Search? State its advantages and disadvantages.
Answer:
Defini on:
Linear search is the simplest searching technique. In this method, every element in the list is
compared with the key (required element) one by one un l the key is found or the list ends.
Advantages:
1. Simple to understand and implement.
2. Works for both sorted and unsorted lists.
3. Suitable for small data.
Disadvantages:
1. Very slow for large data sets.
2. Requires more comparisons ( me complexity = O(n)).
3. Not efficient compared to Binary Search.
Q3) What is Bubble Sort? Write its Algorithm.
Answer:
Defini on:
Bubble Sort is a simple sor ng technique in which each pair of adjacent elements is
compared and swapped if they are in the wrong order. The process is repeated un l the list
becomes sorted.
Algorithm:
Step 1: Repeat steps 2 to 4 for i = 0 to n-1
Step 2: For j = 0 to n-i-1
Step 3: If A[j] > A[j+1], then swap A[j] and A[j+1]
Step 4: End For
Step 5: End
Q4) Explain Inser on Sort with Example.
Answer:
Defini on:
Inser on Sort is a technique where we insert elements into their correct posi on, one at a
me, like arranging playing cards in hand.
Algorithm of Inser on Sort:
Step 1: Repeat for i = 1 to n-1
Step 2: Set key = A[i]
Step 3: Compare key with elements before it
Step 4: Shi all elements greater than key to one posi on ahead
Step 5: Insert key into correct posi on
Step 6: End
Example:
Unsorted list = [7, 4, 5, 2]
Pass 1 → [4, 7, 5, 2]
Pass 2 → [4, 5, 7, 2]
Pass 3 → [2, 4, 5, 7]
Sorted list = [2, 4, 5, 7]
Q5) Give four differences between Linear Search and Binary Search.
Answer:
Linear Search Binary Search
Works for sorted and unsorted lists Works only for sorted lists
Time complexity = O(n) Time complexity = O(log n)
Easy and simple to implement More complex than Linear Search
Less efficient for large data Very efficient for large data
Q6) Describe Quick Sort and its Algorithm.
Answer:
Defini on:
Quick Sort is an efficient sor ng algorithm based on the divide and conquer technique. It
selects a pivot element, places all smaller elements on the le of pivot and larger elements
on the right, then recursively sorts the le and right sublists.
Algorithm of Quick Sort:
Step 1: Choose a pivot element.
Step 2: Divide the array into two sub-arrays:
Le sub-array → elements smaller than pivot
Right sub-array → elements greater than pivot
Step 3: Apply Quick Sort on le sub-array
Step 4: Apply Quick Sort on right sub-array
Step 5: Combine sub-arrays to get final sorted array
