Question

In this lab, you will implement Heap Sort algorithm for the same inputs.

For each algorithm, and for each n = 100, 200, 300, 400, 500, 1000, 4000, 10000, measure its running time and number of steps when the input is (1) already sort, i.e. n, n-1, …, 3, 2,1; (2) reversely sorted 1, 2, 3, … n; (3) random permutation of 1, 2, …, n; (4) 50 instances of n random numbers generated in the range of [1..n].

Note:

(1) You may have to repeat the algorithm many times, each time you need to initialize the array.

(2) Your running time should exclude the time for initialization.

(3) All measurement should be done in a single run, i.e. you do not need to run once for n=100, another time for n=200, etc

IMPORTANT BELOW

********Report the number of steps and the CPU running time in a table.

********Approximation the constant c in the complexity of heap sort (cnlgn) by inspecting the results.

********Well documented source code in C++​​​​​​​

Answer 1

Heap sort is a comparison based sorting technique based on binary heap data structure.it is similar to selection sort where we first find the maximum element and place the maximum element at the end. we repeat the same process for remaining element.

c++ program to implement heap sort

* build a max heap using the given data element

*delet the root node repeatedly.

*store the node at the end of the array.

*display the result.

*exit

Aim :implement heap sort.

ALGORITHM

step 1 :start

step 2: declare the function select.

step 3:read the size of first array as n.

step 4:assign i<-0.

step 5 : check(i<n) if yes do the following step from 6 to 7,otherwise go to step8.

step 6: read the element as a[i].

step 7: calculate i <- i+1.

step 8: call the function select with the argument a,n to sort the array.

step 9: read the size of a second array as m.

step 10: assign j<-0.

step 11:check (j<m),if yes do the following step from 12 to 13,otherwise go to step 14.

step 12:read the elements as b[j].

step 13:calculate j<-j+1.

step 14: call the function select with the argument b,m to sort the array.

step 15: assign i<-0.

step 16: check (i<n),if yes do the following step from 17 to 18 ,otherwise go to step 19.

step 17: print the first sorted array as a[i].

step 18: calculate i<-i+1.

step 19: assign i<-0.

step 20: check(i<m) if yes do the following step from 21 to 22,otherwise go to step 23.

step 21: print the second sorted array as b[i].

step 22: calculate i<-i+1.

step 23: assign i<-0,j<-0,k<-0.

step 24 :check(i<n&&j<m) if yes do the following step from 25 to 29 ,otherwise go to step 30.

step 25: check (a[i]<=b[j]) if yes do the following step from 26 to 27,otherwise go to step 28.

step 26:assign c[k]=a[i].

step 27: calculate i<-i+1.

step 28: assign c[k]=b[j].

step 29: calculate j<-j+1.

step 30: chek(i<n) if yes do the following step from 31 to 32 ,otherwise go to step34.

step 31: assign c[k]=b[j].

step 32:calculate j <-j+1.

step 33:calculate k<-k+1.

step34 : assign i <-0.

step 35 : check (i<n+m) if yes do the following step from 36 to 38 ,otherwise go to step 39.

step 36:print the array after heap sort is c[i].

step 37:print to next line.

step 38: calculate i<-i+1.

step 39:stop.

Definition of function select(i,j,t,n)

step 1:start.

step 2:assign i<-0.

step 3: check (i<n) if yes do the following step from 4 to 11,otherwise go to step 12.

step 4: assign j<- i+1.

step 5:check(j<n) if yes do the following step from 6 to 10,otherwise go to step 11.

step 6:check (a[i]>a[j]),if yes do the following step from 7 to 9,otherwise go to step 10.

step 7: calculate t<-a[j].

step 8:calculate a[j]<-a[i].

step 9:calculate a[i]<-t.

step 10:calculate j<-j+1.

step 11:calculate i<-i+1.

step 12:stop.