Quicksort

Quicksort is an in-place Sorting algorithm. […] It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

(“Quicksort” 2022)

Quicksort is:

• Unstable sorting algorithm
• Internal memory algorithm

Algorithm

This partition algorithm always uses the rightmost element as the pivot. There are other possible pivot selection strategies.

procedure f(lowIndex, highIndex, list) is
  if lowIndex >= highIndex || lowIndex < 0 then
    return

  pivotIndex = partition(0, len(list))

  f(0, pivotIndex-1, list)
  f(pivotIndex+1, len(list), list)

procedure partition(lowIndex, highIndex, list) is
  pivotIndex = highIndex

  i = lowIndex - 1
  for j from lowIndex to highIndex - 1 do
    if list[j] <= list[pivotIndex] then
      i += 1
      swap list[i] and list[j]
  i += 1
  swap list[i] and list[pivotIndex]
  return i

Implementation

• Quicksort implementation in Python

Complexity

Bibliography

Backlinks

• Internal memory algorithm
• Quickselect
• Quicksort implementation in Python
• Unstable sorting algorithm