Question

You have been given the following set of keys

12, 45, 1, 9, 67, 230, 78, 64, 450, 436, 123, 6, 12, 90

1. Use insertion to sort the elements in ascending and descending order ( show the steps)

    [5 Marks]

2. Using heaps, show how the keys can be sorted in ascending and descending order ( show the steps)

     [5 Marks]

3. Using Big O, derive the space and time complexity of insertion sort and heap sort algorithms above

Answer 1

Ans-Insertion sort -

insertion sort is a simple sorting algorithm. this algorithm used insert each element onto its proper place in the sorted array and less efficient than other sort algorithm.

complexity-o(n^2)

Algorithm-

Insertion-sort(A)

{

for j=2 to A.length

key=A[j]

//insert A[j] into sorted sequence A[1.....j-1]

i=j-1

while(i>0 and A[j]>key)

A[i+1]=A[i]

i=i-1

A[i+1]=key

}

descending order-12,45,1,9,67,230,78,64,450,436,123,6,12,90

1,12,45,9,67,230,78,64,450,436,123,6,12,90 (inserted 1)

1,9,12,45,67,230,78,64,450,436,123,6,12,90 ( inserted 9)

1,9,12,45,67,78,230,64,450,436,123,6,12,90 ( inserted 67)

1,9,12,45,64,67,78,230,450,436,123,6,12,90 (inserted 78)

1,9,12,45,64,67,78,230,436,450,123,6,12,90 (" 123)

1,9,12,45,64,67,78,123,230,436,450,6,12,90(" 230)

1,6,9,12,45,64,67,78,123,230,436,450,12,90( "430)

1,6,9,12,12,45,,64,67,78,123,230,436,450,90

1,6,9,12,12,45,64,67,78,90,123,230,436,450(sorted array)

Ascending order-1,6,9,12,12,64,67,78,90,123,436,450

Heap sort- is a comparison based sorting based on binary heap structure it is similar to selection sort.

Algorithm-

1. build a max heap from the input data

2.At this point the largest item is stored at root of heap.

3.Replace it with the last item of the heap followed by reducing the size of heap by 1 finally ,heapify the root of the tree.

4. repeat step 2 while size of heap is greater than 1.

Insertion sort space complexity=o(1)

Heap sort space complexity=o(1)

complexity-o(log n)

build heap complexity=o(nlog n)