Data Structures and Algorithms: Quick Sort

These flashcards cover essential concepts and differences related to Quick Sort and Merge Sort, including their algorithms, complexities, and characteristics.

What is the first step in the Quick Sort algorithm?

Pick any element p as the pivot.

What does the Quick Sort algorithm do after selecting a pivot?

Partition the remaining elements into FirstPart (elements < p) and SecondPart (elements ≥ p).

What is the base case for the Quick Sort algorithm?

If left index is greater than or equal to right index.

What is the worst-case time complexity of Quick Sort?

Θ(n²) occurs when the input is sorted or reversely sorted.

What is the average case time complexity of Quick Sort?

Θ(n log n).

How does Quick Sort differ from Merge Sort in terms of additional space usage?

Quick Sort is an in-place sort and does not require additional space, while Merge Sort requires Θ(n) space.

What is the function Merge(A, left, middle, right) used for in Merge Sort?

It combines two sorted subarrays into a single sorted array.

In Merge Sort, what condition determines when to stop recursion?

When left index is greater than or equal to right index.

What is a key advantage of Quick Sort over Merge Sort?

Quick Sort is faster in the average case due to less overhead in inner loops.

What is the purpose of the Partition function in Quick Sort?

To rearrange the elements around a pivot and return the index of the pivot.