Heap Sort: Difference between revisions
Jump to navigation
Jump to search
| (8 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[ | * [[Algorithms#Sorting_Algorithms|Algorithms]] | ||
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]] | * [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]] | ||
* [[Heap#Canonical_Uses_of_a_Heap|Heaps]] | |||
=Overview= | =Overview= | ||
{| | {| class="wikitable" style="text-align: left;" | ||
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || | | [[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]] || | ||
| Line 16: | Line 17: | ||
=Algorithm= | =Algorithm= | ||
For each element we need to sort, insert it in a [[Heap#Min_Heap_and_Max_Heap|min heap]], using the heap's <tt>[[Heap#INSERT|INSERT]]</tt> operation. The running time of an individual <tt>INSERT</tt> 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 <tt>[[Heap#REMOVE-MIN|REMOVE-MIN]]</tt> 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). | |||
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).