Quicksort
Quicksort is a comparison-based sorting algorithm that partitions elements around a pivot and recursively sorts the resulting subranges.
Grokking Algorithms, Second Edition
Quicksort is a comparison-based sorting algorithm that partitions a sequence around a pivot and recursively sorts the partitions.
- How it is used
- Uses quicksort to demonstrate divide and conquer through a practical sorting algorithm.
- How deep it goes
- Works through partitioning, a recursive Python implementation, and pivot-dependent running time and stack depth.
- Examples
- Sorts a three-element array, implements quicksort in Python, and contrasts pivot choices on an already sorted array.
- What you can do after
- Build it from scratch for an array and choose a random pivot for O(n log n) average running time.
Read how Grokking Algorithms, Second Edition explains quicksort →
Software Design for Python Programmers
Quicksort is a comparison-sorting algorithm that selects a pivot, partitions values around it, and recursively sorts the resulting sublists.
- How it is used
- Uses recursion to sort lists efficiently for ordered output and searchable records.
- How deep it goes
- Descends through pivot partitioning, index movement, swaps, base cases, recursive calls, and a complete Python implementation.
- Examples
- Demonstrates pivot 7 in a sorting trace, pivot 52 during partitioning, and twenty randomly generated Python values.
- What you can do after
- Build it from scratch as an in-place Python sorter with recursive partitioning and sortedness verification.
Read how Software Design for Python Programmers explains quicksort →
Object-Oriented Software Design in C++
Quicksort is a divide-and-conquer sorting algorithm that partitions an array around a pivot and recursively sorts the resulting subarrays.
- How it is used
- Uses recursion to rapidly sort arrays by reducing one problem to independently sortable subarrays.
- How deep it goes
- Descends from algorithm steps through index-level partitioning and C++ member functions, without discussing alternative pivot strategies.
- Examples
- Demonstrates pivot traces, partition swaps, recursive subarrays, and a random twenty-element C++ test array.
- What you can do after
- Build it from scratch using recursive sort, partition, swapping, verification, and array-printing functions.
Read how Object-Oriented Software Design in C++ explains quicksort →
Related concepts
- pivotuses · In partitioning, a pivot is a selected element whose value divides other elements into groups according to their relation to it.
- machine learningkind of · Machine learning is a field of computational methods in which systems learn patterns or relationships from data to make predictions, decisions, or other outputs.
- dataset splituses · A dataset split is the division of a dataset into distinct subsets assigned different purposes, such as training, validation, or testing.
- recursionuses · Recursion is a computational technique in which a definition or procedure refers to or invokes the same definition or procedure, directly or indirectly.
- sorting algorithmkind of · A sorting algorithm is a procedure that rearranges elements of a collection into an order determined by an ordering criterion.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.