Quick Sort

Quick Sort is a sorting algorithm that uses the principle “divide-et-empera” for sorting, it’s one of most used sorting algorithms nowadays. In 90’s there was discovered a defect in C implementation of quicksort that caused sorting complexity to be higher than expected one.

The difference between quick sort and merge sort is that quick sort does the work before recursion, merge sort enters in recursive calls before doing the work. The idea is simple but for me wasn’t very simple to understand because of recursion work done, it toke time and repetitive tries until I understood how it works.

Steps are:

0. Shuffle the array

1. Choose a pivot index K

2. Move all elements smaller that array[K] at the right of K – this is the most important step and is called partitioning. It’s important that K’th element is in place:

• no larger entry to the left of K
• no smaller entry to the right of K

2. Sorting – recursively call the partitioning function for the left ( low index, k ) and for the right ( K, higher index ) sub-arrays.

Partitioning

Phase I

1. Scan i from left to right as long as a[i] < a[lo]
2. Scan j from right to left as long as a[j] > a[lo]
3. Exchange a[j] with a[i]

Phase II – When pointer i and j cross

1. Exchange a[lo] with a[j]

Quicksort it self is a recursive program that uses partition method. The Shuffle is need so that we can guarantee that the performance is good. The partitioning does the partitioning and tell us what elements in position, then sort calls sorting for the left side and right side elements.