Sorting.py

import time
import matplotlib.pyplot as plt

def insertionSort(array):
    steps = 0
    start = time.time()
    for a in range(1,len(array)):
        steps+=1
        key = array[a]
        b = a-1
        while b>=0 and array[b]>key:
            steps+=1
            array[b+1]=array[b]
            b-=1
        steps+=1
        array[b+1]=key
    end = time.time()
    return (array, end-start, steps)

def bubbleSort(array):
    steps = 0
    start = time.time()
    for j in range(len(array),1, -1):
        steps +=1
        for i in range(j-1):
            steps +=1
            if array[i] > array[i+1]:
                steps +=1
                h = array[i]
                array[i] = array[i+1]
                array[i+1]=h
    end = time.time()
    return (array, end-start, steps)

def selectionSort(array):
    steps=0
    start = time.time()
    for a in range(len(array)):
        steps+=1
        mini = a
        for b in range(a+1,len(array)):
            steps+=1
            if array[b] < array[mini]:
                steps+=1
                mini = b
        h = array[a]
        array[a]=array[mini]
        array[mini] = h
    end = time.time()
    return (array, end-start, steps)

# Plot for number of steps       
plt.plot([3,9,15,18, 30],[selectionSort([3,2,1])[2],selectionSort([9,8,7,6,5,4,3,2,1])[2],selectionSort([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2],selectionSort([18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2],selectionSort([30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2]], 'r--')
plt.plot([3,9,15,18, 30],[insertionSort([3,2,1])[2],insertionSort([9,8,7,6,5,4,3,2,1])[2],insertionSort([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2],insertionSort([18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2], insertionSort([30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2]], 'b--')
plt.plot([3,9,15,18, 30],[bubbleSort([3,2,1])[2],bubbleSort([9,8,7,6,5,4,3,2,1])[2],bubbleSort([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2],bubbleSort([18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2], bubbleSort([30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[2]], 'g--')
plt.legend(['Selection Sort', 'Insertion Sort', 'Bubble Sort'])
plt.title('Number of steps X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Number of steps')
plt.show()

# Plot for running time
plt.plot([3,9,15,18, 30],[selectionSort([3,2,1])[1],selectionSort([9,8,7,6,5,4,3,2,1])[1],selectionSort([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1],selectionSort([18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1],selectionSort([30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1] ], 'r--')
plt.plot([3,9,15,18, 30],[insertionSort([3,2,1])[1],insertionSort([9,8,7,6,5,4,3,2,1])[1],insertionSort([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1],insertionSort([18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1],insertionSort([30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1]], 'b--')
plt.plot([3,9,15,18, 30],[bubbleSort([3,2,1])[1],bubbleSort([9,8,7,6,5,4,3,2,1])[1],bubbleSort([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1],bubbleSort([18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1],bubbleSort([30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1])[1]], 'g--')
plt.legend(['Selection Sort', 'Insertion Sort', 'Bubble Sort'])
plt.title('Running Time X Input Size')
plt.xlabel('Input Size')
plt.ylabel('Running Time')
plt.show()



print(selectionSort([4,2,7,10,8,6,1,3,9,5,18,15,12,11,13,16,14,17]))
print(insertionSort([4,2,7,10,8,6,1,3,9,5,18,15,12,11,13,16,14,17]))
print(bubbleSort([4,2,7,10,8,6,1,3,9,5,18,15,12,11,13,16,14,17]))

Graphs comparing each sorting algorithm for different input sizes