# Sorting: Quick Sort

Algorithms Sorting

In this, last in the series, post I will implement probably on of the best known sorting algorithm - Quick Sort. The idea of the in-place algorithm is as follows:

- randomize initial list
- select first element as partition value
- scan i from left to right so long as current element is less than partition value
- scan j from right to left so long as current element is more than partition value
- exchange i-indexed element with j-indexed element
- repeat until i and j cross
- exchange first element with j-indexed element
- split list into two sub-lists bounded by j-indexed partition
- recursively repeat until list contains one or zero elements

After each iteration when first element is exchanged with j-indexed element following invariant should be valid: elements to left are smaller or equal than partition value and elements to the right are bigger or equal. We can visualize quick sort algorithm by sorting following list [3 5 4 7 2 1]. I’ll use colors to specify partition value, current i-indexed element and current j-indexed element.

Iteration #1
[3 5 4 7 2 1] → [3 5 4 7 2 1] → [3 5 4 7 2 1] → [3 **1** 4 7 2 **5**]
[3 1 4 7 2 5] → [3 1 4 7 2 5] → [3 1 **2** 7 **4** 5]
[3 1 2 7 4 5] → [3 1 2 7 4 5] → [3 1 2 7 4 5] → [**2** 1 **3** 7 4 5]

Iteration #2
[ [2 1] 3 [7 4 5] ] → [ [2 1] 3 [7 4 5] ] → [ [2 1] 3 [7 4 5] ] → [ [**1** **2**] 3 [7 4 5] ]

Iteration #3 [ [1] [2] 3 [7 4 5] ] → [1 [2] 3 [4 7 5] ]

Iteration #4 [1 [2] 3 [7 4 5] ] → [1 2 3 [7 4 5] ]

Iteration #5
[1 2 3 [7 4 5] ] → [1 2 3 [7 4 5] ] → [1 2 3 [7 4 5] ] → [ 1 2 3 [7 4 5] ] → [1 2 3 [**5** 4 **7**] ]

Iteration #6
[1 2 3 [5 4] 7] → [1 2 3 [5 4] 7] → [1 2 3 [5 4] 7] → [1 2 3 [**4** **5**] 7]

Iteration #7 [1 2 3 [4] [5] 7] → [1 2 3 4 [5] 7]

Iteration #8 [1 2 3 4 [5] 7] → [1 2 3 4 5 7]

For the sake of easiness I’ll skip list randomization step. Implementation of the quick sort heavily rely on sort and partition functions:

**Complexity:** O(n·logn).