Heap Sort: Difference between revisions
Jump to navigation
Jump to search
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
* [[Algorithms#Sorting_Algorithms|Algorithms]] | * [[Algorithms#Sorting_Algorithms|Algorithms]] | ||
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]] | * [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]] | ||
* [[Heap# | * [[Heap#Canonical_Uses_of_a_Heap|Heaps]] | ||
=Overview= | =Overview= | ||
{| class="wikitable" style="text-align: left;" | {| class="wikitable" style="text-align: left;" | ||
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || O(n | | [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || O(n log n) | ||
|- | |- | ||
| [[Algorithm_Complexity#Average-case_Running_Time|Average-case time]] || | | [[Algorithm_Complexity#Average-case_Running_Time|Average-case time]] || | ||
Latest revision as of 23:58, 19 October 2021
Internal
Overview
| Worst-case time | O(n log n) |
| Average-case time | |
| Best-case time |
Algorithm
For each element we need to sort, insert it in a min heap, using the heap's INSERT operation. The running time of an individual INSERT is O(log n), so the insertion in a loop will have a running time of O(n log n). Once all the elements that need to be sorted are placed in the min heap, extract the minimum element from the heap, also in a loop, with REMOVE-MIN and place it in order in the final array. The running time of the second phase is O(n log n). The total running time is O(n log n).