Learn Computer Science

Quick Sort

Tutoring > Data Structures > Quick Sort

Quick sort is a comparison based, divide and conquer sorting algorthim for sorting arrays.

The idea behind the quick sort algorithm is to ​pick a "pivot" element to re-order the other elements around, and recursively apply the same steps to the resultant smaller sub-arrays. The base case for this recursion is when the array is size 1 or 0, this is when we will have a sorted array. A base case when talking about recursive algorithms is what causes the algorithm to stop running.

 

The time complexity for the worst case is O(n^2).

The time complexity on average is O(nlog(n)).

 

• We wil start with this array: {20, 13, 7, 17, 1, 3, 5, 18, 19, 12, 11, 10, 9}

• Next we choose a suitable pivot. Since we have no idea what any element is, we can choose any to start. Some people decide to try and find a good pivot to improve efficiency but we will just pick the middle value of the array : 

 

20, 13, 7, 17, 1, 3, 15, 18, 19, 12, 11, 10, 9

^    

 

• Next we arrange all the elements smaller than the pivot to the left of it, and all the elements larger to the right.  So now we split the array:

 

11, 13, 7, 9, 1, 3 , 10, 12     15     18, 19, 20, 17

 

• and choose pivots for each of these sub-arrays:

 

11, 13, 7, 9, 1, 3 , 10, 12     15     18, 19, 20, 17

    ^                                                 ^

 

• Next we perform the same step as above, splitting the arrays into smaller arrays with the smaller elements left, and larger right:

 

11, 13, 7, 9, 1, 3 , 10, 12     15     18, 19, 20, 17  becomes

1, 3, 7     9     10, 11, 13, 12     15     17, 18     19   20

 

• Repeat the steps, choosing a pivot from the sub-araays and dividing them according to value until you just have single elemetns left:

 

1, 3, 7     9     10, 11, 13, 12     15     17, 18     19   20

   ^                         ^                               ^                     ^

1     3     7     10     11     12, 13     15     17     18     19     20

 

1     3     7     10     11     12, 13     15     17     18     19     20

   ^            ^      ^                  ^                                  ^                      

• Finally we have all the elements sorted. This happens when no more pivots can be chosen. It is the base case of the recursive algorithm.

 

{1, 3, 7, 9, 10, 11, 12, 13, 15, 17, 18, 19, 20}