## Overview

Its similar to Merge Sort where we apply divide and conquer approach but unlike Merge sort there is no need to combine because Quicksort sorts in-place.

## Divide

**Pivot** can be selected by choosing :

- A right most item in the list.
- A randomly selected value is also taken as pivot, the random item is then swapped with the last item in the list.
- A set of three random values are picked, the median value among the 3 is swapped with the last item in the list.
- Items that are less than pivot are collected in left and right if otherwise.
- The above evaluation will not guarantee sorted items in the left or right.

## Conquer

The left and right chunk are repeated applied with the same evaluation.

## Combine

No combine needed unlike merge sort, because the sorting happens in-place.

## Main Method Pseudocode

- function that takes: A (input), p(starting index), r(pivot's index)
- if p ≥ r then do nothing
- get q(dividing line between the left and right chunk) by partitioning
- invoke the main method with the left chunk with (A, p, q-1) as parameters
- invoke the main method with the right chunk with (A, q+1, r) as parameters

## Partition Pseudocode

- function that takes: A(input), p(starting index), r(pivot's index)
- set q as p
- loop through the input
- check if the current value of the input is less than the pivot
- then swap the current value with the q

- after the loop, swap the r with the q ( this put the pivot in between the left and right chunks)

## Code

```
var A = [5, 4, 3, 1, 4, 53, 1, 4, 6, 3, 7, 3, 11, 2, 1, 5, 7, 3]
function quicksort(A, p, r) {
if (p >= r) return
var q = partition(A, p, r)
quicksort(A, p, q - 1)
quicksort(A, q + 1, r)
}
function partition(A, p, r) {
var q = p
for (var u = p; u <= r - 1; u++) {
if (A[u] <= A[r]) {
;[A[q], A[u]] = [A[u], A[q]]
q++
}
}
;[A[q], A[r]] = [A[r], A[q]]
return q
}
quicksort(A, 0, A.length - 1)
console.log(A)
```