Question

Define a heap. Describe the algorithm to insert an element into the heap. 

Answer 1

Insertion Sort Algorithm: 

Consider an array 'A' with 'N' 

elements

1. set A[0]=-infinity [initialize sentinel element]

2. Repeat steps 3 to 5 for K=2,3..,.......N

3. set TEMP=A[K] and PTR=K-1 4 Repeat while TEMP <A[PTR]

(a) set A[PTR+1]=A[PTR] [moves element forward] 

(b) set PTR=PTR-1 [End of loop]

5. set A[PTR+1]=TEMP [inserts elements in proper place] 

[End of step2 loop]

6. Return

Complexity of insertion sort

Worst case: The worst case occurs when the -array 'A' is in reverse order and the inner loop must use the max number K-1 of comparisons. Hence

F(n)= 1 + 2+........+(n-1)=n(n-1)/2=0(n² )

Average case: In Average case there will be approximately (K-1)/2 comparisons in the inner loop. Accordingly, for the average case,

F(n)=1/2+2/2+........ ...+(n-1)/2=n(n-1)/4=0(n² )