Scribd
Upload
0 views2 pages

02 Quick Sort Notes

Quick Sort is a divide-and-conquer sorting algorithm that partitions an array around a selected pivot, recursively sorting the resulting partitions. Its time complexity is O(n log n) on average, but can degrade to O(n²) in the worst case, while the space complexity averages O(log n). Quick Sort is advantageous for its fast average performance and in-place sorting, but its efficiency is heavily influenced by pivot selection and it is not stable.

Uploaded by

votolet376
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0 views2 pages

02 Quick Sort Notes

Quick Sort is a divide-and-conquer sorting algorithm that partitions an array around a selected pivot, recursively sorting the resulting partitions. Its time complexity is O(n log n) on average, but can degrade to O(n²) in the worst case, while the space complexity averages O(log n). Quick Sort is advantageous for its fast average performance and in-place sorting, but its efficiency is heavily influenced by pivot selection and it is not stable.

Uploaded by

votolet376
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Design and Analysis of Algorithms

Quick Sort
Study Notes: Quick Sort

Definition
Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot and partitions the array around
that pivot.

Basic Idea
Elements smaller than the pivot are placed on one side and larger elements on the other side. The same
process is recursively applied to the two partitions.

Steps
• Choose a pivot.

• Partition the array around the pivot.

• Place the pivot in its correct position.

• Recursively sort the left partition.

• Recursively sort the right partition.

Example
For [8, 3, 1, 7, 0, 10, 2], selecting 7 as a pivot separates smaller elements from larger elements. The
partitions are then sorted recursively.

Time Complexity
Best Case: O(n log n) Average Case: O(n log n) Worst Case: O(n²)

Space Complexity
Average recursion space is O(log n); worst case can reach O(n).

Advantages
• Fast average performance.

• Works in-place with suitable partitioning.

• Usually good cache performance.

Disadvantages
• Worst-case time is O(n²).

• Performance depends on pivot selection.


• Not stable in its common in-place form.

Applications
General-purpose in-memory sorting, database systems, and applications requiring fast average-case
sorting.

Exam Tip: Remember the definition, basic idea, algorithm steps, complexity, advantages, disadvantages,
and applications.

You might also like