Question

Part 2: coding question and timing experiment. You may use code from the textbook. Heapsort vs Treesort In part two, you will compare the performance of two new sorting algorithms (heapsort and treesort). Treesort is an algorithm that works by first creating a BST from the unsorted input sequence, and then outputting the sorted result by applying an inorder traversal to the BST. Heapsort works by first building a heap from the unsorted input sequence, and then repeatedly calling deleteMin on the heap until the heap is empty, outputting the result of each deleteMin into the sorted array. Part 2a: write C++ code to perform heapsort and treesort on an array of n=100000 randomly generated numbers. You can use the code from the textbook for the BST and heap, but you will need to add more code to complete the sorting experiments (for example, you will need to add the inorder traversal method to the BST). Part 2b: repeat 2a, but use an AVL tree instead of a BST for treesort. Part 2c: discuss the results of heapsort and treesorts vs other sorting algorithms (quicksort, mergesort).

Answer 1

The task is to implement and compare the performance of heapsort and treesort using binary search trees and AVL trees on an array of large random data. Then, compare these algorithms to other sorting methods like quicksort and mergesort.

Step-by-step explanation:

The task involves implementing two sorting algorithms, heapsort and treesort, on a dataset of n=100,000 randomly generated numbers in C++. For treesort, you'll need to create a binary search tree (BST) from the input and then perform an inorder traversal to get the sorted output. For heapsort, a heap is built from the dataset followed by repeatedly calling deleteMin until the heap is empty.

In part 2b, you'll replace the BST in treesort with an AVL tree, which is a self-balancing BST, and compare its performance. Finally, you'll discuss the results of these sorting methods in comparison with other common sorting algorithms like quicksort and mergesort. The AVL tree should yield better performance for treesort on average due to better balance, while heapsort is typically more consistent than treesort given that AVL tree balancing can incur additional operations.

Code Snippets for Heapsort and Treesort

--Heapsort Implementation--

--Treesort Implementation using BST--

--Treesort Implementation using AVL Tree--