# Quick Sort

Sep 22, 2012 · Commentscode sortingalgoc++

Quick Sort is an efficient divide and conquer algorithm performed in two phases - partition and sorting phase.

Here are few pointers to remember about Quick Sort:

- Partitioning places all the elements less than the pivot in the left part of the array and greater elements in the right part
- Pivot element stays in its place
- After partitioning no element moves to the other side, of the pivot
- * This allows you to sort the elements, to the left or right of the pivot, independent of the other side
- Complexity is O(n log n)
- Often fast for small arrays with a few distinct values, repeated many times
- It is a conquer-and-divide algo; with most of the work happening during partitioning phase
- If you had to choose the optimum pivot then it should the median of the given array
- Not a stable sort

## Testing Notes

- Currently we have only one version of the code. We may try to do another version that is not recursive because putting the functions on stack will take up some memory and time
- Another version could be trying to use the pivot from the middle and then compare how do the random numbers compare against the sorted numbers

## Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

## Numbers

**# of Items in Array** | **Time Taken** | **Average for 100 numbers** | |

**Random** | 10 | 0.072972 | 0.72972 |

1K | 2.74698 | 0.274698 | |

1M | 4640.77 | 0.464077 | |

**Sorted** | 10 | 0.042773 | 0.42773 |

1K | 1.84335 | 0.184335 | |

1M | 2473.42 | 0.247342 |