Heap Sort: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(6 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Internal=
=Internal=


* [[Data Structures and Algorithms#Sorting_Algorithms|Data Structures and Algorithms]]
* [[Algorithms#Sorting_Algorithms|Algorithms]]
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]]
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]]
* [[Heap#Overview|Heaps]]
* [[Heap#Canonical_Uses_of_a_Heap|Heaps]]


=Overview=
=Overview=


{|
{| class="wikitable" style="text-align: left;"
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || O(n lgn)
| [[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 17: Line 17:
=Algorithm=
=Algorithm=


=Time Complexity Analysis=
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).