# 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.

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>leftList:
tmp = leftList
leftList = leftList
leftList = tmp

if len(rightList)>2:
rightList = mergeSort(rightList)
else:
if len(rightList)==2:
if rightList>rightList:
tmp = rightList
rightList = rightList
rightList = 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, 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.

Did you like this challenge?

Click on a star to rate it!

Average rating 4.8 / 5. Vote count: 20

No votes so far! Be the first to rate this post.

As you found this challenge interesting...