PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q4

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Why do you need external sorting? Sort the following elements using max heap and also analyse its computational complexity. 42, 36, 56, 27, 63, 72, 62, 15

Solution

Need for External Sorting: External sorting is required when the dataset to be sorted is too large to fit inside main memory (RAM) and must reside on secondary storage (HDD/SSD). Because disk I/O is orders of magnitude slower than RAM, external sorting (such as external -way merge sort) splits data into memory-sized sorted runs and merges them sequentially to minimize disk block transfers.

Building the Max-Heap from [42, 36, 56, 27, 63, 72, 62, 15]: Last non-leaf index is :

Extraction and Heapify-Down Passes:

  1. Swap root 72 with 15, heapify size 7 [63, 36, 62, 27, 15, 56, 42 | 72].
  2. Swap root 63 with 42, heapify size 6 [62, 36, 56, 27, 15, 42 | 63, 72].
  3. Swap root 62 with 42, heapify size 5 [56, 36, 42, 27, 15 | 62, 63, 72].
  4. Swap root 56 with 15, heapify size 4 [42, 36, 15, 27 | 56, 62, 63, 72].
  5. Swap root 42 with 27, heapify size 3 [36, 27, 15 | 42, 56, 62, 63, 72].
  6. Swap root 36 with 15, heapify size 2 [27, 15 | 36, 42, 56, 62, 63, 72].
  7. Swap root 27 with 15, size 1 [15, 27, 36, 42, 56, 62, 63, 72].

Computational Complexity of Heap Sort:

Answer:

All past exam questions for Data Structure and Algorithms