concept · INFO-CS-ADS-133Quick Sort
Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot, partitions elements around it, and recursively sorts the resulting sections. It is often very fast in practice but has quadratic worst-case time complexity.
Explanation
Overview
Quick Sort is a comparison-based sorting algorithm that rearranges elements around a selected pivot so that smaller elements appear on one side and larger elements appear on the other side, according to the chosen partitioning scheme.
Purpose
Its purpose is to sort collections efficiently using partitioning and recursive processing. It is widely studied because of its practical speed and its relationship with divide-and-conquer algorithms.
Key concepts
name: Core idea; description: The central focus of quick sort is the capability described here: Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot, partitions elements around it, and recursively sorts the resulting sections. It is often very fast in practice but has quadratic worst-case time complexity.; name: Problem context; description: Quick Sort is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using quick sort, check its assumptions, input requirements, expected output, and resource constraints.
Space complexity
In-place partitioning can use O(log n) average recursion-stack space for balanced partitions. Worst-case recursion depth can reach O(n) when partitions are highly unbalanced.
Example
For [8, 3, 1, 7, 0, 10, 2], selecting 7 as a pivot allows the algorithm to partition smaller values to one side and larger values to the other. It then recursively sorts the resulting sections until the array becomes [0, 1, 2, 3, 7, 8, 10].
Pseudocode
QUICK_SORT(A, low, high):
if low < high:
pivotIndex = PARTITION(A, low, high)
QUICK_SORT(A, low, pivotIndex - 1)
QUICK_SORT(A, pivotIndex + 1, high)
PARTITION(A, low, high):
pivot = A[high]
i = low - 1
for j = low to high - 1:
if A[j] <= pivot:
i = i + 1
swap(A[i], A[j])
swap(A[i + 1], A[high])
return i + 1
Advantages
Usually performs very well on arrays.; Common implementations require little additional data storage beyond the recursion stack.; Uses cache-friendly sequential partitioning in many implementations.; Has O(n log n) average-case time complexity.; Supports different pivot-selection and partitioning strategies.
Example or application
For [8, 3, 1, 7, 0, 10, 2], selecting 7 as a pivot allows the algorithm to partition smaller values to one side and larger values to the other. It then recursively sorts the resulting sections until the array becomes [0, 1, 2, 3, 7, 8, 10].
Definition
Quick Sort is a comparison-based sorting algorithm that rearranges elements around a selected pivot so that smaller elements appear on one side and larger elements appear on the other side, according to the chosen partitioning scheme.
Purpose
Its purpose is to sort collections efficiently using partitioning and recursive processing. It is widely studied because of its practical speed and its relationship with divide-and-conquer algorithms.
Pivot
The pivot is the element or selected value used to divide the collection into partitions. The quality of the pivot influences how balanced the partitions become.
Pivot Selection Methods
First element: Selects the first element as the pivot.
Last element: Selects the final element as the pivot.
Middle element: Selects an element near the middle position.
Random pivot: Selects a pivot randomly to reduce sensitivity to particular input arrangements.
Median-of-three: Selects the median among the first, middle, and last elements as a practical pivot strategy.
Partitioning
Partitioning rearranges elements so that values satisfying one side of the pivot condition appear before or after the pivot region. The exact arrangement depends on the partition scheme, such as Lomuto or Hoare partitioning.
Algorithm Steps
Select a pivot from the current section.
Partition the section according to the pivot.
Identify the resulting smaller sections.
Recursively sort the left section.
Recursively sort the right section.
Continue until all sections contain zero or one element.
Pseudocode
QUICK_SORT(A, low, high):
if low < high:
pivotIndex = PARTITION(A, low, high)
QUICK_SORT(A, low, pivotIndex - 1)
QUICK_SORT(A, pivotIndex + 1, high)
PARTITION(A, low, high):
pivot = A[high]
i = low - 1
for j = low to high - 1:
if A[j] <= pivot:
i = i + 1
swap(A[i], A[j])
swap(A[i + 1], A[high])
return i + 1
Best Case
O(n log n) time when partitions are consistently balanced or reasonably close to balanced.
Average Case
O(n log n) time for typical random or well-behaved input arrangements under common pivot strategies.
Worst Case
O(n²) time when partitioning repeatedly produces highly unbalanced sections, such as one section containing nearly all elements and the other containing very few.
Space Complexity
In-place partitioning can use O(log n) average recursion-stack space for balanced partitions. Worst-case recursion depth can reach O(n) when partitions are highly unbalanced.
Stability
Standard in-place Quick Sort is unstable because partitioning can move equal-key elements past one another. Stable Quick Sort variants are possible but usually require additional storage or a different partitioning method.
In Place Property
Common Quick Sort implementations rearrange elements within the original array through partitioning. However, recursive calls still use additional stack memory.
Partition Schemes
Lomuto partition scheme: Commonly uses one pivot at the end of the section and moves qualifying elements toward one boundary.
Hoare partition scheme: Uses two scanning positions that move inward and exchange elements that are on the wrong sides of the pivot.
Pivot Quality
Balanced partitions reduce recursion depth and produce efficient performance. Poor pivot choices can create highly unbalanced partitions and increase the number of comparisons.
Advantages
Usually performs very well on arrays.
Common implementations require little additional data storage beyond the recursion stack.
Uses cache-friendly sequential partitioning in many implementations.
Has O(n log n) average-case time complexity.
Supports different pivot-selection and partitioning strategies.
Limitations
Has O(n²) worst-case time complexity.
Standard in-place implementations are unstable.
Performance depends on pivot selection and partition balance.
Poor recursion behavior can increase stack usage.
Requires careful partition-boundary management.
Optimization Techniques
Randomized pivot selection.
Median-of-three pivot selection.
Insertion Sort for very small partitions.
Three-way partitioning for collections with many duplicate values.
Tail-recursion optimization or recursion-depth controls.
Practical Applications
Sorting arrays and in-memory collections.
General-purpose sorting implementations.
Sorting data when average practical performance is important.
Teaching partition-based divide-and-conquer techniques.
Common Errors
Returning an incorrect pivot position.
Using inconsistent partition boundaries.
Recursively processing a section that still includes the pivot.
Failing to handle duplicate values appropriately.
Choosing a poor pivot repeatedly for structured input.
Implementation Considerations
The partition function must maintain its chosen invariant and return a valid boundary. Recursive calls should exclude any pivot region already placed in its final position.
Key Takeaway
Quick Sort is an efficient practical sorting algorithm based on pivot selection and partitioning. Its average performance is O(n log n), but careful pivot strategies and recursion management are important to avoid quadratic behavior.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of quick sort is the capability described here: Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot, partitions elements around it, and recursively sorts the resulting sections. It is often very fast in practice but has quadratic worst-case time complexity. |
Problem context | Quick Sort is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using quick sort, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of quick sort? | Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot, partitions elements around it, and recursively sorts the resulting sections. It is often very fast in practice but has quadratic worst-case time complexity. |
What should be checked before applying quick sort? | For quick sort, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of quick sort be validated? | Trace a representative quick sort case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of quick sort.
Identify the assumptions, inputs, and conditions relevant to quick sort.
Evaluate an application of quick sort for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures