Home/Coding Guide/Sorting Algorithms — Deep Dives
⌂ Main Page
Coding Interview Preparation Guide

Sorting Algorithms — Deep Dives

Each classic sorting algorithm explained and implemented from scratch: bubble, selection, insertion, shell, merge, and quick sort.

Challenges on this page

01Bubble Sort

Source notebook: Bubble Sort Udemy.ipynb

Implementation of a Bubble Sort

The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.

Resources for Review

Check out the resources below for a review of Bubble sort!

Python
def bubble_sort(arr):
    # For every element (arranged backwards)
    for n in range(len(arr)-1,0,-1):
        #
        for k in range(n):
            # If we come to a point to switch
            if arr[k]>arr[k+1]:
                temp = arr[k]
                arr[k] = arr[k+1]
                arr[k+1] = temp
Python
arr = [3,2,13,4,6,5,7,8,1,20]
bubble_sort(arr)
Python
arr
Output
[1, 2, 3, 4, 5, 6, 7, 8, 13, 20]

Great Job!

02Selection Sort

Source notebook: Selection Sort Udemy.ipynb

Implementation of Selection Sort

The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place. After the second pass, the next largest is in place. This process continues and requires n−1 passes to sort n items, since the final item must be in place after the (n−1) st pass.

Resources for Review

Check out the resources below for a review of Selection sort!

Python
def selection_sort(arr):
    
    # For every slot in array
    for fillslot in range(len(arr)-1,0,-1):
        positionOfMax=0
        
        # For every set of 0 to fillslot+1
        for location in range(1,fillslot+1):
            # Set maximum's location
            if arr[location]>arr[positionOfMax]:
                positionOfMax = location

        temp = arr[fillslot]
        arr[fillslot] = arr[positionOfMax]
        arr[positionOfMax] = temp
Python
arr = [3,5,2,7,6,8,12,40,21]
selection_sort(arr)
arr
Output
[2, 3, 5, 6, 7, 8, 12, 21, 40]

Good Job!

03Insertion Sort

Source notebook: Insertion Sort Udemy.ipynb

Implementation of Insertion Sort

Insertion Sort builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Resources for Review

Check out the resources below for a review of Insertion sort!

Python
def insertion_sort(arr):
    
    # For every index in array
    for i in range(1,len(arr)):
        
        # Set current values and position
        currentvalue = arr[i]
        position = i
        
        # Sorted Sublist
        while position>0 and arr[position-1]>currentvalue:
            
            arr[position]=arr[position-1]
            position = position-1

        arr[position]=currentvalue
Python
arr =[3,5,4,6,8,1,2,12,41,25]
insertion_sort(arr)
arr
Output
[1, 2, 3, 4, 5, 6, 8, 12, 25, 41]

Good Job!

04Shell Sort

Source notebook: Shell Sort Udemy.ipynb

Implementation of Shell Sort

The shell sort improves on the insertion sort by breaking the original list into a number of smaller sublists, each of which is sorted using an insertion sort. The unique way that these sublists are chosen is the key to the shell sort. Instead of breaking the list into sublists of contiguous items, the shell sort uses an increment i, sometimes called the gap, to create a sublist by choosing all items that are i items apart.

Resources for Review

Check out the resources below for a review of Shell sort!

Python
def shell_sort(arr):
    sublistcount = len(arr)/2
    
    # While we still have sub lists
    while sublistcount > 0:
        for start in range(sublistcount):
            # Use a gap insertion
            gap_insertion_sort(arr,start,sublistcount)

      

        sublistcount = sublistcount / 2

def gap_insertion_sort(arr,start,gap):
    for i in range(start+gap,len(arr),gap):

        currentvalue = arr[i]
        position = i

        # Using the Gap
        while position>=gap and arr[position-gap]>currentvalue:
            arr[position]=arr[position-gap]
            position = position-gap
        
        # Set current value
        arr[position]=currentvalue
Python
arr = [45,67,23,45,21,24,7,2,6,4,90]
shell_sort(arr)
arr
Output
[2, 4, 6, 7, 21, 23, 24, 45, 45, 67, 90]

Good Job!

05Merge Sort

Source notebook: Merge Sort Udemy.ipynb

Implementation of Merge Sort

Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.

Resources for Review

Check out the resources below for a review of Merge sort!

Python
def merge_sort(arr):
    
    if len(arr)>1:
        mid = len(arr)/2
        lefthalf = arr[:mid]
        righthalf = arr[mid:]

        merge_sort(lefthalf)
        merge_sort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                arr[k]=lefthalf[i]
                i=i+1
            else:
                arr[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            arr[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            arr[k]=righthalf[j]
            j=j+1
            k=k+1
Python
arr = [11,2,5,4,7,6,8,1,23]
merge_sort(arr)
arr
Output
[1, 2, 4, 5, 6, 7, 8, 11, 23]

Good Job!

06Quick Sort

Source notebook: Quick Sort Udemy.ipynb

Implementation of Quick Sort

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

Resources for Review

Check out the resources below for a review of Insertion sort!

Python
def quick_sort(arr):
    
    quick_sort_help(arr,0,len(arr)-1)

def quick_sort_help(arr,first,last):
    
    if first<last:
        

        splitpoint = partition(arr,first,last)

        quick_sort_help(arr,first,splitpoint-1)
        quick_sort_help(arr,splitpoint+1,last)


def partition(arr,first,last):
    
    pivotvalue = arr[first]

    leftmark = first+1
    rightmark = last

    done = False
    while not done:

        while leftmark <= rightmark and arr[leftmark] <= pivotvalue:
            leftmark = leftmark + 1

        while arr[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            done = True
        else:
            temp = arr[leftmark]
            arr[leftmark] = arr[rightmark]
            arr[rightmark] = temp

    temp = arr[first]
    arr[first] = arr[rightmark]
    arr[rightmark] = temp


    return rightmark
Python
arr = [2,5,4,6,7,3,1,4,12,11]
quick_sort(arr)
arr
Output
[1, 2, 3, 4, 4, 5, 6, 7, 11, 12]

Good Job!