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.
Insertion SortBubble SortMerge SortQuick Sort
Insertion Sort Algorithm
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)
Bubble Sort Algorithm
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 Algorithm
#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 Algorithm
#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 (leftPointerpivotValue: 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.