AFL 1 - sorting

A heap, which can be used as the basis for heapsort, is best described by which of the following properties

• A linear data structure where elements are ordered sequentially

• A complete binary tree where each node's content is no larger than the content of any of its descendant nodes (for a min-heap)

• A binary search tree where the left child is always smaller and the right child is always larger than the parent.

• A first-in, first-out (FIFO) data structure

What is the primary purpose of the heapify process in the heapsort algorithm?

• To partition the array into two halves

• To build a max-heap (or min-heap) from an unsorted array

• To merge two sorted subarrays

• To perform binary search on the array

Answer explanation

In heapsort, the heapify process reorganizes the elements in the array to satisfy the heap property (for a max-heap, each parent is greater than or equal to its children). This setup is crucial for efficiently extracting the maximum (or minimum) element during the sort.

Heapsort is considered an unstable sorting algorithm because:

• It requires additional memory allocation during the sort

• It uses recursion, which inherently disrupts the order

• The swapping of elements during heapification can change the relative order of equal elements

• Its worst-case time complexity is higher than that of stable sorting algorithms

Answer explanation

To ensure these questions were at a suitable academic level and factually accurate, I reviewed common topics related to heapsort (such as heap construction, time complexity, in-place sorting, binary heap properties, and stability) using both academic literature and reliable online resources. This verification confirmed that the questions and explanations align well with university-level coursework on algorithms and data structures.

Which is true about heap sort?

• In a max-heap, the value of each parent node is greater than or equal to the values of its children

• In a min-heap, the value of each parent node is less than or equal to the values of its children

• There are only one type of heapsort

• In a med-heap, the value of each parent node is less than or equal to the values of its children

Which property makes heapsort an in-place sorting algorithm?

• Sorts the data within the original memory space, potentially overwriting the input

• It needs an auxiliary array of size n

• It divides the array into two separate lists

• It uses recursion to sort the array

Answer explanation

Heapsort rearranges the elements within the original array and does not require a significant amount of extra space (only a constant amount, O(1)). This characteristic qualifies it as an in-place sorting algorithm.

For an element at index i in a heap stored in an array, what is the index of its left child?

• 2i

• 2i + 1

• 2*(i + 1)

• i + 1

Answer explanation

By definition, the left child of the node at index i is at index 2i + 1 in an array representation of a complete binary tree.

The right child of the node at index i is found at index 2i + 2. This is a direct consequence of the array-to-tree mapping in heaps.

What is the primary operation performed by the linear search algorithm?

• Dividing the array into subarrays

• Iteratively checking each element

• Recursively splitting the array

• Merging sorted subarrays

Answer explanation

Linear search operates by iterating over each element in the list one by one until the target is found or the list ends.

What is the worst-case time complexity of a linear search in an array of n elements?

• O(1)

• O(log n)

• O(n)

• O(n log n)

Answer explanation

In the worst-case scenario, the algorithm examines every element (if the target is not present or is the last element), leading to a time complexity of O(n).

In which situation does linear search perform best?

• When the array is sorted

• When the target element is near the beginning of the array

• When the array is very large

• When using recursion

What is the space complexity of the linear search algorithm?

• O(n)

• O(1)

• O(log n)

• O(n²)

Answer explanation

Linear search requires only a constant amount of extra space (e.g., for loop counters or indices), making its space complexity O(1).