Python code for Time complexity plot of Heap sort
In this tutorial, we will write the Python program for the time complexity plot of heap sort.
Heap:
A heap is a complete binary tree where the value of parent is greater than its child nodes (Max Heap) or is smaller than its child nodes (Min Heap).
The sorting algorithm that uses Heap to sort the elements is called heap sort. The formula 2*i is used to calculate the position of the left child and that of the right child, 2*i+1.
To visualize the time complexity of the heap sort, we will implement heap sort a list of random integers. Python matplotlib.pyplot is used to plot the graph and NumPy to generate random integers. time.process_time() gives the sum of user space CPU and the kernel time.
So below is our Python code for Time complexity plot of Heap sort
import time import numpy as np import matplotlib.pyplot as plt def maxheap(a,i): l=2*i r=2*i +1 n= len(a)-1 if(l<=n and a[l]>a[i]): large=l else: large=i if(r<=n and a[r]>a[large]): large=r if(large!=i): temp=a[i] a[i]=a[large] a[large]=a[i] maxheap(a,large) def build_heap(a): leaf=int(len(a)/2) for i in range(leaf -1, -1, -1): maxheap(a, i) def heapsort(a): build_heap(a) n= len(a)-1 for i in range(int(n),0,-1): a[i],a[0]=a[i],a[0] #easy way to swap elements directly n=n-1 maxheap(a,0) dict1={} #using dictionary to store the time taken by each set of elements for i in range(1,10): a=np.random.randint(0,i*5000,i*1000) st=time.process_time() heapsort(a) end=time.process_time() dict1[len(a)]=(end-st) print("Time taken by " + str(len(a)) + " numbers is " + str(dict1[len(a)])) print("Following graph depicts the Time Complexity plot for heap sort:") plt.xlabel("Elements in a heap") plt.ylabel("Time") plt.title("Heap Sort Time Complexity") plt.plot(*zip(*sorted(dict1.items()))) plt.show()
Output of the above program and Time Complexity Plot:
Time taken by 1000 numbers is 0.006170349999999658 Time taken by 2000 numbers is 0.017003724000000275 Time taken by 3000 numbers is 0.015554909999999644 Time taken by 4000 numbers is 0.016545511000000346 Time taken by 5000 numbers is 0.016028323000000455 Time taken by 6000 numbers is 0.021886925000000446 Time taken by 7000 numbers is 0.022509170999999384 Time taken by 8000 numbers is 0.026082438999999624 Time taken by 9000 numbers is 0.030361662999999872 Following graph depicts the Time Complexity plot for heap sort:
Time Complexity of heap sort is O(n log(n)).
Applications of HeapSort:
Leave a Reply