# Quick Sort

** Updated:**

## If we say that main idea of Merge sort is recursively merge, then the quick sort is just recursively partitioning.

___ MIT

## 1. Intuition

Let A be the array we want to sort. Firstly, we partition A into 3 sets:

**Pivot set**: A singleton set that only contains the pivot; (the pivot is usually the last element in the current array portion`A[r]`

)**Greater set**: Contains the elements from`A[i+1] to A[j - 1]`

which are all greater than the pivot;**Less & Equal set**: Contain the elements from`A[p] to A[i]`

which are all less and equal to the pivot.

### $ *Loop invariant (Three conditions):*

*Loop invariant (Three conditions):*

### $ *Maintenance:*

*Maintenance:*

## 2. Pseudocode

```
-- choose the last item as the pivot --
algorithm QuikSort(array, start, end):
if start < end then
pivot_i = Partition(array, start, end)
QuikSort(array, start, pivot_i-1)
QuilSort(array, pivot_i+1, end)
function Partition(array, start, end):
pivot = array[end]
i = start - 1
For j := start to (end-1) do
if array[j] ≤ pivot then
i = i + 1 --> array[i] is included in the smaller-set so we need to increase it before the exchange
Exchange array[i] with array[j]
Exchange array[i+1] with array[end]
return i+1
```

*Tips*: What hapens if p == r?

## If p == r, then

`A[j] == pivot`

and when`i++`

,`i = j = r`

so that the first exchange`A[i]`

with`A[j]`

operation will be useless and (i+1) in both second exchange operation and the return statement will cause array out of range.

## 3. Time Complexity

## The running time of quicksort depends on whether the partitioning is balanced or unbalanced, which in turn depends on which elements are used for partitioning.

- Balanced partitioning :≈ merge sort
- Unbalanced partitioning :≈ insertion sort

### (1) Unbalanced Partitioning (Worst case):

The worst-case behaviour for quicksort occurs when the partitioning routine produces one subproblem with n 1 elements and one with 0 elements.

\(T(n) = T(n-1) + T(0) + \Theta(n) \\
= T(n-1) + \Theta(n)\)
Then, we can use **subsitution method** to prove that:
\(T(n) = T(n-1)+\Theta(n) \\
= \Theta(n^2)\)

### (2) Best Partitioning (Best case):

In the most even possible split, PARTITION produces two subproblems, each of size no more than n=2, since one is of size floor(n/2) and one of size (ceil(n/2)-1). In this case, quicksort runs much faster.\(T(n) = 2T(n/2) + \Theta(n)\) By case 2 of the master theorem (Theorem 4.1), this recurrence has the solution: \(T(n) = \Theta(nlgn)\)

### (3) Balanced Partitioning (Average case)

Any split of

constant proportionalityyields a recursion tree of depth Θ(lgn) where the cost at each level is O(n)

The running time is, therefore, O(nlgn) whenever the split hasconstant proportionality

*Tips: Intuition for average-case*

*Tips: Intuition for average-case*

- For a random input array, the partitioning is different at every level;
- The average-case ≈ a mix of “good” and “bad” partitioning (good: constant proportionality; bad: unbalanced);
- The “good” and “bad” splits are distributed randomly through the tree.
- The depth of the tree is always O(lgn) and O(n) work is performed at each level.

(bad+good ≈ good)

## Code

```
// Scala
object QuickSortAlgo {
def quickSort(array: Array[Double], start: Int, end: Int): Unit = {
if (start < end) {
var pivot_i = partition(array, start, end)
quickSort(array, start, pivot_i-1)
quickSort(array, pivot_i+1, end)
}
}
def partition(array: Array[Double], start: Int, end: Int): Int = {
var pivot = array(end)
var i = start - 1
for (j <- start until end) {
if (array(j) < pivot) {
i += 1
// swap
var tmp = array(i)
array(i) = array(j)
array(j) = tmp
}
}
var tmp = array(i+1)
array(i+1) = array(end)
array(end) = tmp
return i+1
}
def main(args: Array[String]): Unit = {
var array = Array(4234,234234,23,234,-134,4123,41,578,-342,55,0.2323,0.325)
println("\nBefore sorting:")
println(array.deep.mkString(" "))
quickSort(array, 0, array.length-1)
println("\nAfter sorting:")
println(array.deep.mkString(" "))
}
}
```

```
# Python
def partition(array, start, end):
pivot = array[end]
i = start - 1
for j in range(start, end):
if array[j] <= pivot:
i += 1
array[i], array[j] = array[j], array[i]
array[i+1], array[end] = array[end], array[i+1]
return i+1
def quick_sort(array, start, end):
if start < end:
pivot_i = partition(array, start, end)
quick_sort(array, start, pivot_i-1)
quick_sort(array, pivot_i+1, end)
if __name__ == "__main__":
array = [4234,234234,23,234,-134,123,41,578,-342,55,0.9323,0.325]
# array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print("Before sorting: ", array)
quick_sort(array, 0, len(array)-1)
print("After sorting: ", array)
```

## Leave a comment