Q.Which of the following sorting algorithms has the worst time complexity of nlog(n)?
Correct answer: Heapsort
Explanation
Heapsort is a comparison - based sorting algorithm which can be thought of as implementation of selection sort using the right data structure. In heap sort, we use binary heap so that we can quickly find and move the max element in O (log n) instead of O (n) and hence achieve the O (n log n) time complexity.
Heapsort is a comparison - based sorting algorithm which can be thought of as implementation of selection sort using the right data structure. In heap sort, we use binary heap so that we can quickly find and move the max element in O (log n) instead of O (n) and hence achieve the O (n log n) time complexity.