# Quicksort

0
40

Quicksort is a sorting algorithm that picks an element (“the pivot”) and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted – from Wikipedia.

## Quicksort Basics

Time Complexity

• O(n^2) Worst case performance
• O(n log n) Best-case performance
• O(n log n) Average performance

Space Complexity

• O(log(n)) Worst case

### Approach

• Make the right-most index value pivot
• Partition the array using pivot value
• Quicksort left partition recursively
• Quicksort right partition recursively

### 1. Lomuto partition scheme mechanism

This scheme chooses a pivot which is typically the last element in the array. The algorithm maintains the index to put the pivot in variable i and each time it ﬁnds an element less than or equal to pivot, this index is incremented and that element would be placed before the pivot.

Quick Sort mechanism:

### 2. Hoare partition scheme

It uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater or equal than the pivot, one lesser or equal, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the ﬁnal index. Hoare’s scheme is more eﬃcient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates eﬃcient partitions even when all values are equal.

Partition:

## Quicksort Implementation

### Python Implementation

You may also like:

This site uses Akismet to reduce spam. Learn how your comment data is processed.