PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Provide best case, average case and worst case for following algorithms in Big-Oh: bubble sort, insertion sort, merge sort and selection sort. Construction heap sort for following given list with an algorithm: 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22.

Solution

Asymptotic Time Complexity Comparison:

AlgorithmBest CaseAverage CaseWorst Case
Bubble Sort (with early-exit flag)
Insertion Sort
Merge Sort
Selection Sort

Heap Sort Algorithm:

Algorithm HEAPSORT(A, n):
1. For i = floor(n/2) - 1 down to 0:
       HEAPIFY(A, n, i)       // Build max-heap
2. For end = n - 1 down to 1:
       Swap A[0] and A[end]
       HEAPIFY(A, end, 0)     // Restore max-heap on A[0..end-1]

Trace on [37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22] ():

Answer:

All past exam questions for Data Structure and Algorithms