Question

4)

Course: Programming Fundamentals III

Textbook: A Practical Introduction to Data Structures and Algorithm Analysis Edition 3.2 (C++ Version)

Question: Write a short comparison paragraph (not an essay) about 'Heap sort vs. Bubble sort'.

Answer 1

Comparison between Heap sort vs Bubble sort.

Heap sort uses complete Binary tree for sorting whereas Bubble sort do not require binary tree at all. The best, worst, average case for heap sort time complexity is O(nlogn) irrespective of how the data is stored, for bubble sort time complexity varies according to how the data is stored, the best time complexity is O(n) when the data is already sorted, worst case is O(n^2) when the data is reversed sorted, the average case is when the data is randomly distributed with time complexity of O(n^2).  Heap sort will be preferred over Bubble sort for average case, when we do not know how the data is stored.

Hope it answers your question.

Any doubt, do comment.