Option 3 : Divide and Conquer

RSEB Informatics Assistant (RVUNL) Computer Science - Mini Mock Test

3731

70 Questions
100 Marks
60 Mins

The correct answer is **option 3**

__Key Points__

- Quicksort is an efficient sorting algorithm also known as a partition-exchange sort
- Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation is defined
**Quicksort is a divide-and-conquer algorithm in which the pivot element is chosen, and this pivot element reduced the given problem into two smaller set**- In the efficient implementations, it is not a stable sort, meaning that the relative order of equal sort items is not preserved
- Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting

__Additional Information__

Quicksort:

In Quicksort, the worst-case takes Θ (n2) time. The worst case of quicksort is when the first or the last element is chosen as the pivot element.

Diagram

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.

Recurrence relation for quick sort algorithm will be,

T (n) = T (n-1) + Θ (n)

This will give the worst-case time complexity as Θ (n2).