1. Randomized quick sort is a stable sort.
a) true
b) false
Explanation: Randomized quick sort like standard quick sort is also not a stable sorting algorithm. It is because the elements with the same values are not guaranteed to appear in the same relative order in the output sorted array.
2. What is the best case time complexity randomized quick sort?
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
Explanation: Best case time complexity is given in the case when there is equal partitioning of the array about the pivot. It is given by the relation T(n) = 2T(n/2) + n which gives the result O(n log n).
3. Which of the following is incorrect about randomized quicksort?
a) it has the same time complexity as standard quick sort
b) it has the same space complexity as standard quick sort
c) it is an in-place sorting algorithm
d) it cannot have a time complexity of O(n2) in any case.
Explanation: Randomized quick sort prevents the worst case complexity of O(n2) in most of the cases. But in some rare cases the time complexity can become O(n2). The probability of such a case is however very low.
4. What is the worst case time complexity of randomized quicksort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
Explanation: Randomized quicksort prevents the worst case complexity of O(n2) in most of the cases. But in some rare cases the time complexity can become O(n2). The probability of such a case is however very low.
5. What is the other name for a shell sort algorithm?
a) Diminishing increment sort
b) Diminishing decrement sort
c) Insertion sort
d) Selection sort
Explanation: The other name for a shell sort algorithm is diminishing decrement sort as the distance between comparisons decreases as the algorithm runs until the last phase.
6. The worst case running time of shell sort, using Shell’s increments is?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Explanation: The lower bound of a shell sort algorithm is mathematically found to be O(N2).
7. Who invented the shell sort algorithm?
a) John Von Neumann
b) Donald Shell
c) Tony Hoare
d) Alan Shell
Explanation: Shell sort algorithm is invented by Donald shell. Merge sort is invented by John Von Neumann. Quick sort is invented by Tony Hoare.
8. Shell sort algorithm is the first algorithm to break the quadratic time barrier.
a) True
b) False
Explanation: Shell sort broke the quadratic time barrier as it works by comparing elements that are distant.
9. Shell sort algorithm is an example of?
a) External sorting
b) Internal sorting
c) In-place sorting
d) Bottom-up sorting
Explanation: Shell sort is an example of internal sorting because sorting of elements is done internally using an array.
10. Shell sort uses a sequence called a incrementing sequence to sort the elements.
a) True
b) False
Explanation: Shell sort uses an increment sequence h1, h2, h3… and this sequence will work as long as h1=1.
Design and Analysis of Algorithms
The Prelude to Sorting Symphony
In the grand theater of algorithms, sorting is like orchestrating a symphony. Each element plays a note, and Shell Sort steps in as the charismatic conductor, waving its wand to create harmony. But what makes it so special?
Breaking Down the Algorithmic Ballet
You have a list of elements, and you want to arrange them in ascending or descending order. Shell Sort, also known as the diminishing increment sort, is your magical wand. It's a smart cookie, starting with larger gaps and gradually narrowing them down until the list is nearly sorted.
The Dance of Gaps
In Shell Sort, gaps are the choreography that dictates the movement of elements. The algorithm begins with a big leap, comparing elements that are far apart. Then, it progressively shrinks the gap, creating a mesmerizing dance of data until, voilà, everything is in order.
Why Shell Sort Rules the Sorting Ball
Unlike some other sorting algorithms, Shell Sort doesn't just move elements one step at a time. It's like giving your data a dance partner that can waltz across the list, making it faster and more efficient.
Wrapping Up the Algorithmic Soirée
In the grand finale of our sorting symphony, Shell Sort takes a bow, leaving behind an ordered array of applause. The design and analysis of algorithms, intertwined with MCQs, applaud this sorting maestro for its dance of efficiency.
So, next time you're pondering the algorithmic universe, remember Shell Sort – the magical conductor orchestrating the data ballet with elegance and precision. Keep sorting, keep dancing, and let the algorithmic show go on!