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<len(leftList) and rightPointer<len(rightList):
    if leftList[leftPointer] < rightList[rightPointer]:
       sortedList.append(leftList[leftPointer])
       leftPointer += 1
    else:   
       sortedList.append(rightList[rightPointer])
       rightPointer += 1
  
  while leftPointer<len(leftList):
    sortedList.append(leftList[leftPointer])
    leftPointer+=1
  while rightPointer<len(rightList):
    sortedList.append(rightList[rightPointer])
    rightPointer+=1
    
  return sortedList

#Quick Sort: Another divide-and-conquer algorithm implemented using a recursive function!
def quickSort(list, leftPointer, rightPointer):
  # Use the mid value as the pivot
  pivotPointer = leftPointer + ((rightPointer-leftPointer) // 2)
  
  # Alternative approach: use the first value as the pivot
  #pivotPointer = leftPointer
  
  # Alternative approach: use the last value as the pivot
  #pivotPointer = rightPointer
  
  print("Pivot: " + str(list[pivotPointer]))
  left_Pointer = leftPointer
  right_Pointer = rightPointer
  
  while leftPointer<rightPointer:
    #Find the next value to swap (left side of the pivot)
    while list[leftPointer]<=list[pivotPointer] and leftPointer<pivotPointer:
      leftPointer = leftPointer+1
      
    #Find the next value to swap (right side of the pivot)
    while list[rightPointer]>=list[pivotPointer] and rightPointer>pivotPointer:
      rightPointer = rightPointer-1  
    
    if leftPointer<rightPointer:  
      #Swap both values 
      tmp = list[leftPointer]
      list[leftPointer] = list[rightPointer]
      list[rightPointer] = tmp
      #Has the pivot moved?
      if leftPointer == pivotPointer:
        pivotPointer = rightPointer
      elif rightPointer == pivotPointer:
        pivotPointer = leftPointer
  
  print(list)
  # Let's implement the double recursion to quick sort both sub lists on the left and the right of the pivot Pointer
  if pivotPointer-1-left_Pointer>=1: #Stop the recursion if there is only on value left in the sublist to sort
    quickSort(list,left_Pointer,pivotPointer-1)
  if right_Pointer - (pivotPointer+1)>=1: #Stop the recursion if there is only on value left in the sublist to sort
    quickSort(list,pivotPointer+1,right_Pointer)

Full Python Code

See below the full code for all four sorting algorithms.