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<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 Algorithm
#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.
With this approach, all the leaf nodes (nodes without sub-branches) are the prime factors of the root node. For instance, with the above tree, the prime factors of 150 are 2, 3, 5 and 5 again. In other words:
LMC Simulator
Logic Gates Circuits
Network Designer
Flowchart Studio
Online Python IDE