Quicksort

As explained in 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.

Quicksort sorts by choosing a pivot, partitioning values around it, and recursively sorting the sublists on either side. The pivot reaches its final position during partitioning. section 15.6

Apply the algorithm in this sequence:

• Choose a pivot, move it aside, and scan inward with indexes i and j. section 15.6.2
• Swap out-of-place values while i remains left of j, then restore the pivot between the two sublists. section 15.6.2
• Stop for sublists of size zero or one; swap a reversed pair of size two; otherwise recurse on both sides. section 15.6

Python implementation

A Quicksort class separates swapping, partitioning, recursive sorting, and verification. Its demonstration sorts twenty random values in place and reports success after checking adjacent pairs. section 15.6.3

Figure 15.12 Choosing 52 (circled) to be the pivot value and then partitioning the list into two sublists. Variables i and j are list indexes. After partitioning, all values to the left of 52 are less than or equal to it, and all values to the right of 52 are greater. The two boxed sublists on either side of the pivot are now ready to be recursively quicksorted.

Follow the pivot 52 through index scans and swaps to see how one list becomes two recursively sortable sublists. section 15.6.2

How Software Design for Python Programmers covers it

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 it assumes

Assumes lists, indexes, comparisons, swapping, and recursion; teaches the partitioning process and its stopping cases.

What you can do after

Build it from scratch as an in-place Python sorter with recursive partitioning and sortedness verification.

How it connects

Connects sorting with recursion, partitioning, pivots, sublists, indexes, and base cases.

liveBookmanning.com

Read Software Design for Python Programmers on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionQuicksort is a comparison-based sorting algorithm that partitions a sequence around a pivot and recursively sorts the partitions.
• 

  liveBookmanning.com
  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.

Compare how 3 books explain 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.

This explainer was generated by Manning's knowledge graph from the text of Software Design for Python Programmers. The section links point to the parts of the book it draws on.