W3205 Quick Sort

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Background

• Read Quick Sort Algorithm (Wikipedia)
• View Quick Sort Algorithm (YouTube)
• View Quick Sort Algorithm (YouTube)

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.