1. What is an internal sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Explanation: As the name suggests, internal sorting algorithm uses internal main memory.
2. What is the worst case complexity of bubble sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: Bubble sort works by starting from the first element and swapping the elements if required in each iteration.
3. What is the average case complexity of bubble sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: Bubble sort works by starting from the first element and swapping the elements if required in each iteration even in the average case.
4. Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case of sorted elements?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) Consumes less time
Explanation: Optimised Bubble sort is one of the simplest sorting techniques and perhaps the only advantage it has over other techniques is that it can detect whether the input is already sorted. It is faster than other in case of sorted array and consumes less time to describe whether the input array is sorted or not. It consumes same memory than other sorting techniques. Hence it is not an advantage.
5. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
a) 4
b) 2
c) 1
d) 0
Explanation: Even though the first two elements are already sorted, bubble sort needs 4 iterations to sort the given array.
6. What is the best case efficiency of bubble sort in the improvised version?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n).
7. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?
a) 4
b) 2
c) 1
d) 0
Explanation: Only 2 elements in the given array are not sorted, hence only 2 iterations are required to sort them.
8. Merge sort uses which of the following technique to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Explanation: Merge sort uses divide and conquer in order to sort a given array. This is because it divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together.
9. What is the average case time complexity of merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Explanation: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. It is found to be equal to O(n log n) using the master theorem.
10. What is the auxiliary space complexity of merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Explanation: An additional space of O(n) is required in order to merge two sorted arrays. Thus merge sort is not an in place sorting algorithm.
Design and Analysis of Algorithms
The Bubble Sort Shimmy
Imagine you're at a dance party, and everyone is chaotically jumbled. Bubble Sort decides to tidy up the dance floor by comparing pairs of dancers (elements) and swapping them if they are in the wrong order.
In algorithm lingo, it's like saying, "Hey, are you taller than the person next to you? If yes, let's switch places!" This repeats until everyone is dancing in height order, making the whole party more organized.
The Bubble Sort Banter
Why do we even bother with Bubble Sort when there are flashier algorithms like Quick Sort and Merge Sort? Well, Bubble Sort has its own charm – it's easy to understand and implement. It's like choosing your favorite classic dance move over a complex routine.
In the world of MCQs, understanding Bubble Sort might be your secret weapon. Knowing when to employ it can be the difference between acing an algorithm quiz and doing the robot dance of confusion.
In the grand ballroom of algorithms, each dance has its own flair. Bubble Sort might not be the belle of the ball, but it sure knows how to keep things simple and entertaining. So, next time you're waltzing through the Design and Analysis of Algorithms, don't forget to give Bubble Sort a twirl – you might just find its rhythm to be surprisingly catchy!