Implement the following sorting algorithms Bubble Sort Inser

Implement the following sorting algorithms: Bubble Sort Insertion Sort. Selection Sort. Merge Sort. Heap Sort. Quick Sort. For each of the above algorithms, measure the execution time based on input sizes n, n + 10(i), n + 20(i), n + 30(i), .. ., n + 100(i) for n = 50000 and i = 100. Let the array to be sorted be randomly initialized. Use the same machine to measure all the algorithms. Plot a graph to compare the execution times you collected in part(2).

Solution

This code wil create a graph for each plots comparing time for different sorting methods and also save those plots in the current directory.

from random import shuffle
from time import time
import numpy as np
import matplotlib.pyplot as plt

def bubblesort(arr):
   for i in range(len(arr)):
      for k in range(len(arr)-1, i, -1):
         if (arr[k] < arr[k-1]):
            tmp = arr[k]
            arr[k] = arr[k-1]
            arr[k-1] = tmp
   return arr

def selectionsort(arr):
    for fillslot in range(len(arr)-1,0,-1):
        positionOfMax=0
        for location in range(1,fillslot+1):
            if arr[location]>arr[positionOfMax]:
                positionOfMax = location
        temp = arr[fillslot]
        arr[fillslot] = arr[positionOfMax]
        arr[positionOfMax] = temp
    return arr

def insertionsort(arr):
    for i in range( 1, len( arr ) ):
        tmp = arr[i]
        k = i
        while k > 0 and tmp < arr[k - 1]:
            arr[k] = arr[k-1]
            k -= 1
        arr[k] = tmp
    return arr

# def mergesort(arr):
#
#    if len(arr)>1:
#       mid = len(arr)//2
#       lefthalf = arr[:mid]
#       righthalf = arr[mid:]
#
#       mergesort(lefthalf)
#       mergesort(righthalf)
#
#       i=0
#       j=0
#       k=0
#       while i < len(lefthalf) and j < len(righthalf):
#          if lefthalf[i] < righthalf[j]:
#             arr[k]=lefthalf[i]
#             i=i+1
#          else:
#             arr[k]=righthalf[j]
#             j=j+1
#             k=k+1
#
#       while i < len(lefthalf):
#          arr[k]=lefthalf[i]
#          i=i+1
#          k=k+1
#
#       while j < len(righthalf):
#          arr[k]=righthalf[j]
#          j=j+1
#          k=k+1
#
#    return arr

def mergesort(x):
    result = []
    if len(x) < 2:
        return x
    mid = int(len(x)/2)
    y = mergesort(x[:mid])
    z = mergesort(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
           result.append(z[j])
           j += 1
        else:
           result.append(y[i])
           i += 1
    result += y[i:]
    result += z[j:]
    return result

def quicksort(arr):
    less = []
    equal = []
    greater = []

    if len(arr) > 1:
        pivot = arr[0]
        for x in arr:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return quicksort(less)+equal+quicksort(greater) # Just use the + operator to join lists
    else:
        return arr

#### Heap sort
def heapsort(arr): #convert arr to heap
    length = len(arr) - 1
    leastParent = length / 2
    for i in range(leastParent, -1, -1):
        moveDown(arr, i, length)

    # flatten heap into sorted array
    for i in range(length, 0, -1):
        if arr[0] > arr[i]:
            swap(arr, 0, i)
            moveDown(arr, 0, i - 1)

def moveDown(arr, first, last):
    largest = 2 * first + 1
    while largest <= last: #right child exists and is larger than left child
        if (largest < last) and(arr[largest] < arr[largest + 1]):
            largest += 1

        # right child is larger than parent
        if arr[largest] > arr[first]:
            swap(arr, largest, first)# move down to largest child
            first = largest
            largest = 2 * first + 1
        else:
            return# force exit

def swap(A, x, y):
    tmp = A[x]
    A[x] = A[y]
    A[y] = tmp

def create_array(n):
    arr = [i+1 for i in range(0, n)]
    shuffle(arr)
    return arr

plot_vals = []
for i in range(0, 110, 10):
    n = 50000 + i*100
    times = {}
    vals = []

    #measuring times
    arr = create_array(n)
    a = time()
    arr = bubblesort(arr)
    times[\'bubblesort\'] = time()-a
    vals.append(times[\'bubblesort\'])

    arr = create_array(n)
    a = time()
    arr = insertionsort(arr)
    times[\'insertionsort\'] = time()-a
    vals.append(times[\'insertionsort\'])

    arr = create_array(n)
    a = time()
    arr = selectionsort(arr)
    times[\'selectionsort\'] = time()-a
    vals.append(times[\'selectionsort\'])

    arr = create_array(n)
    a = time()
    arr = mergesort(arr)
    times[\'mergesort\'] = time()-a
    vals.append(times[\'mergesort\'])

    arr = create_array(n)
    a = time()
    arr = heapsort(arr)
    times[\'heapsort\'] = time()-a
    vals.append(times[\'heapsort\'])

    arr = create_array(n)
    a = time()
    arr = quicksort(arr)
    times[\'quicksort\'] = time()-a

    vals.append(times[\'quicksort\'])

    plot_vals.append(vals)
    printstatement = \"Times for input size of n+\"+str(i)+\"(i) = \", times

    print printstatement

fig = plt.figure()
fig.suptitle(\'Times for various sort algorithms based on n\', fontsize=20)
for i in range(11):
    n = 50+1000*i
    colors = [\'b\', \'c\', \'y\', \'m\', \'r\', \'k\']
    times_range = range(0, 200, 10)
    bst = plt.scatter(n, plot_vals[i][0], marker=\'x\', color=colors[0])
    ist = plt.scatter(n, plot_vals[i][1], marker=\'x\', color=colors[1])
    sst = plt.scatter(n, plot_vals[i][2], marker=\'x\', color=colors[2])
    mst = plt.scatter(n, plot_vals[i][3], marker=\'x\', color=colors[3])
    hst = plt.scatter(n, plot_vals[i][4], marker=\'x\', color=colors[4])
    qst = plt.scatter(n, plot_vals[i][5], marker=\'x\', color=colors[5])
    print i
    plt.legend((bst, ist, sst, mst, hst, qst),
         (\'Bubble Sort \'+str(n), \'Insertion sort \'+str(n), \'Selection Sort \'+str(n), \'Merge Sort \'+str(n), \'Heap Sort \'+str(n), \'Quick Sort \'+str(n)),
            scatterpoints=1,
            loc=\'lower left\',
            ncol=3,
            fontsize=8)

file_name = \'sort_times.jpg\'
fig.savefig(file_name)
plt.show()