Chapter 11: Sorting

Question 1

If an array arr = {55, 42, 4, 31} is given and bubble sort is used to sort the array elements, then how many passes will be required to sort the array?

1. 3
2. 2
3. 1
4. 0

Solution

The answer is a. To sort n elements, the bubble sort algorithm requires (n-1) iterations (passes), where n is the number of elements in the given array. Here in the question, the value of n = 4, so 4-1 = 3 iterations will be required to sort the given array.

Question 2

What is the worst-case complexity of bubble sort?

1. O(nlogn)
2. O(logn)
3. O(n)
4. O(n²)

Solution

The answer is d. The worst case appears when the given array is in reverse order. In that case, the time complexity of bubble sort would be O(n²).

Question 3

Apply quicksort to the sequence (56, 89, 23, 99, 45, 12, 66, 78, 34). What is the sequence after the first phase, and what pivot is the first element?

1. 45, 23, 12, 34...