Question

Coding question and timing experiment

a: write C++ code to perform heapsort and treesort on an array of = 100000 randomly generated numbers. (you will need to add the inorder traversal method to the BST).
b: repeat 2a, but use an AVL tree instead of a BST for treesort
c: discuss the results of heapsort and treesorts vs other sorting algorithms (quicksort, mergesort)

Answer 1

This task involves implementing heapsort and treesort in C++ for a large data set and comparing these sorting algorithms to others such as quicksort and mergesort, with a focus on their time complexity and space requirements.

Step-by-step explanation:

The question pertains to writing C++ code to perform heapsort and treesort on an array of 100,000 randomly generated numbers, and then to compare the performance of these sorting algorithms to others like quicksort and mergesort. The task involves implementing two sorting algorithms and an in-order traversal method for a Binary Search Tree (BST) and an AVL tree.

Following the implementation, these sorting methods should be executed to sort the randomly generated array, and their performances need to be analyzed and compared to traditional sorting algorithms. Heapsort is well-known for its guaranteed O(n log n) performance, while treesort's performance can vary from O(n log n) for balanced trees like AVL to O(n^2) in the worst case for unbalanced BSTs.

Heapsort is considered in-place and non-stable, whereas treesort is not in-place but can be stable if implemented carefully. Quicksort is typically fast with average-case complexity of O(n log n), but has a worst-case scenario of O(n^2); mergesort is stable and always has a time complexity of O(n log n), but requires additional space.