# W3205 Quick Sort

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

## Introduction

The quicksort algorithm is generally known as one of the fastest sorting algorithms, many times faster than heap sort. If implemented well, quick sort algorithms can have a complexity of O(n log n)

## Algorithm

The quicksort algorithm calls for a pivot during its recursive calls, here is an overview:

1. Pick an element as a pivot
2. Create 2 markers, which will be compared with a < function in order to set values up for a partition
3. Create a partition, which will be used to put elements in an array smaller than x and greater than x
4. Repeat steps 2 and 3 until the array is sorted

## Choosing a Pivot

The pivot point which is chosen for the partition range and subranges will often determine the o complexity of the sort. Here is a list of common pivot points that are used:

• Leftmost element
• Median element
• Rightmost element
• Randomized element

### Implementation

Quicksort algorithms vary, partitions and pivot elements can be different for each algorithm. The partition and method of obtaining a pivot element usually depend on what is being sorted, and what level of Big O complexity the algorithm is aiming for.

• First, create a partition
• A partition will take the pivot point(x) and put all smaller elements before x, and all larger elements after x
• in order to do this, we will need to keep track of the leftmost and rightmost index with 2 pointers( or markers)
• While traversing elements, if we find a smaller element (an element smaller than x), we will swap the lower element to the left
• Otherwise, if there aren't any smaller elements, we will ignore the current element
• Then recursive calls of these partitions will be made until the array is sorted
Quicksort partition diagram

### Performance

As seen before, the average performance of quicksort is O(n log n) complexity, but how quicksort algorithms work, depends on the method of obtaining a pivot point, and how partitions are made (based on how array elements were originally inputted), quicksort can have a worse case complexity of O(n^2).

## Exercises

Exercises
•  M1352-10  Complete  Merlin Mission Manager  Mission M1352-10.