W3205 Quick Sort

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


Background[edit]


Introduction[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

ExercisesExercisesIcon.png
  •  M1352-10  Complete  Merlin Mission Manager  Mission M1352-10.