A Guide To Quick Sort: Sorting Algorithms

In this tutorial, we are going to be looking at quick sort algorithms, their syntax, and usages.

The quick sort algorithm is a time and memory-efficient sorting algorithm, and knowing this algorithm will give you the ability to solve a wide range of sorting problems.

Let’s get started!

Table of contents

Overview

A quick sort algorithm is built around choosing a pivot element in an array. If we take the example of an array of numbers that need to be sorted in ascending order, a quick sort algorithm will pick one entry (the current element) and compare it to all other entries. The algorithm will then divide the array into two sections. One section will be for entries lower than the selected pivot element and the other will be for entries larger than the pivot element. This is called “partitioning” the array (you may even hear quick sort referred to as a partition algorithm). Pivot values are then picked for those two new sections and the process is repeated for all the elements in the array.

Unlike other sorting algorithms, you can achieve significant increases in accuracy based on how the pivot element is chosen. Some approaches would choose to set the pivot element to be the first entry in the array. Other approaches would choose either the middle element or last element. Some approaches may even decide to choose a random element (though having a random pivot is not usual). Choosing the pivot element is a consideration to be made based on the sorting problem that needs to be solved.

Examples

Here is a visual example:

The dark square is the pivot value. That value is compared with other entries in the list. It is rearranged until entries greater than it are on the right and entries lesser than it are on the left. The process is then repeated on both sides of the pivot with new pivot values chosen for each side. Once the process has finished, we can put the array back together to make a complete, sorted array.

The visual example is one of the ways of constructing the algorithm. In the example, two temporary arrays are created (which does increase space complexity in this case). We can also construct an algorithm that doesn’t create any new arrays. Here is a Python script with a quick sort algorithm in action:

#This function chooses a pivot 
#and moves the pivot into its correct spot

def partition(start, end, array):
  
  #The start of the array is chosen as the pivot

  pivotIndex = start
  pivot = array[pivotIndex]
  
  #This loop places the pivot in 
  #its proper place witin the array

  while start < end:
    
    while start < len(array) and array[start] <= pivot:
      start += 1
      
    while array[end] > pivot:
      end -= 1
    
    #Once the algorithm finds a place where the 'start' 
    #position is greater than the pivot and 
    #where the 'end' is less than the pivot, 
    #those two positions swap

    if(start < end):
      array[start], array[end] = array[end], array[start]
  
  #Swap the pivot with the 'end' position

  array[end], array[pivotIndex] = array[pivotIndex], array[end]
  
  return end
  
# The algorithm function

def quickSort(start, end, array):
  
  if (start < end):
    
    # Parition the array and grab the index

    pIndex = partition(start, end, array)
    
    # Sort each side of the partition

    quickSort(start, pIndex - 1, array)
    quickSort(pIndex + 1, end, array)
    

#Code to implement the algorithm

array = [ 2, 7, 8, 9, 1, 5, 10]
quickSort(0, len(array) - 1, array)
print(array)

First, this algorithm chooses the first entry as a pivot (i.e. the leftmost element). It then loops through the array elements until entries greater than the pivot are on the right, with the greatest being the rightmost element, and smaller elements than the pivot are on the left, with the smallest element being the first element in the array. This partition function is then called by the quickSort function. The quickSort function then calls itself until the array is completely sorted.

Quick sort algorithms are a highly efficient sorting algorithm when it comes to time and memory. A best-case scenario for a quick sort algorithm is when neither the largest nor the smallest value is chosen. If this happens, the algorithm can exit the loop early. This is why choosing the correct element as a pivot is important.

That being said, there are plenty of other sorting algorithms available. Merge sort, for instance, is another time-efficient sorting algorithm which takes a sort of divide and conquer approach with an unsorted array. You also aren’t limited to one programming language with quick sort, so you may wish to try getting sorted data with something like C++ for practice.