Insertion, Bubble, Merge and Quick Sort Algorithms

In computer science, sorting algorithms are used to sort the elements of a data sets in numerical or alphabetical order. In this blog post will investigate the Python code used to implement 4 of the most frequently used sorting algorithms:

• Insertion Sort
• Bubble Sort
• Merge Sort
• Quick Sort

We will implement the first two algorithm using nested loops. (Iterative algorithms) whereas the Merge sort and Quick sort algorithms will be based on using recursive functions to implement the divide-and-conquer approach these algorithms are based on.

def insertionSort(list):
  #Iterate through each value of the list
  for i in range(1,len(list)):
    pointer = i
    
    #Slide value on the left to insert it in postion
    while list[pointer]<list[pointer-1] and pointer>0:
      #Swap values with the previous value...
      tmp=list[pointer]
      list[pointer]=list[pointer-1]
      list[pointer-1] = tmp
      
      pointer = pointer - 1
   
    #Print list at the end of each iteration
    print(list) 

def bubbleSort(list):
  counter = len(list)-1
  sorted=False
  
  #The Bubble sort stops iterating if it did not perform any "swap" in the previous iteration.
  while sorted==False:
    sorted=True
    for pointer in range(0,counter):
      if list[pointer]>list[pointer+1]:
        #Swap values with the next value...
        tmp = list[pointer]
        list[pointer] = list[pointer+1]
        list[pointer+1] = tmp
        sorted=False
    #Print list at the end of each iteration
    print(list)  
    counter-=1

#Merge Sort: A divide-and-conquer algorithm implemented using a recursive function!
def mergeSort(list):
  midPointer = len(list) // 2
  
  leftList = list[0:midPointer]
  rightList = list[midPointer:len(list)]
  
  if len(leftList)>2: 
    leftList = mergeSort(leftList)
  else:
    if len(leftList)==2:
      if leftList[0]>leftList[1]:
        tmp = leftList[0]
        leftList[0] = leftList[1]
        leftList[1] = tmp
       
  if len(rightList)>2: 
    rightList = mergeSort(rightList)
  else:
    if len(rightList)==2:
      if rightList[0]>rightList[1]:
        tmp = rightList[0]
        rightList[0] = rightList[1]
        rightList[1] = tmp
        

  #Merge left and right...'
  leftPointer = 0
  rightPointer = 0
  sortedList=[]
  while leftPointer

#Quick Sort: Another divide-and-conquer algorithm implemented using a recursive function!
def quickSort(list):
  #Initialise the Pivot using the element in middle position of the list
  pivotPointer = len(list)//2
  pivotValue = list[pivotPointer]

  # Initialise the left and right pointer 
  leftPointer = 0 # To point to the first value in the list
  rightPointer = len(list)-1 # To point to the last value in the list
  
  # Sliding the pointers to identify values to swap around: 
  while (leftPointer pivotValue:
      rightPointer = rightPointer - 1

    # If we have identified two values that need to be swapped, we swap them around!
    if  list[leftPointer] >= pivotValue and list[rightPointer] <= pivotValue:
      tmp = list[rightPointer]
      list[rightPointer] = list[leftPointer]
      list[leftPointer] = tmp
      if leftPointer==pivotPointer:
        pivotPointer=rightPointer
      elif rightPointer==pivotPointer:
        pivotPointer=leftPointer
      leftPointer = leftPointer + 1
      rightPointer = rightPointer - 1
      
  # Let's slice the list into two sub-lists:
  # The left sublist contains all the values to the left of the pivot. (Not that all these values are lower than the pivot!)
  if pivotPointer > 0:
      leftList = list[0:pivotPointer]
  else: 
    leftList = []  # In case there is no value to the left of the pointer!

  # The right sublist contains all the values to the right of the pivot. (Not that all these values are greater than the pivot!)
  if pivotPointer < len(list)-1:
      rightList = list[pivotPointer+1:len(list)]
  else:
    rightList=[] # In case there is no value to the right of the pointer!

  #Let's implement the recursive calls with our two sublists!
  if len(leftList)<2: # Stopping condition of the recursive call... if the left list contains 0 and just 1 element!
    sortedLeftList = leftList 
  else:
    sortedLeftList = quickSort(leftList) # Recursive call!
  
  if len(rightList)<2: # Stopping condition of the recursive call... if the right list contains 0 and just 1 element!
    sortedRightList = rightList
  else:
    sortedRightList = quickSort(rightList) # Recursive call!
  
  # Let's now joined the left list, the pivot and the right list together to get a fully sorted list!
  sortedLeftList.append(pivotValue)
  sortedLeftList.extend(sortedRightList)
  return sortedLeftList

Full Python Code

See below the full code for all four sorting algorithms.