- an average and worst-case O(N*LogN) complexity
- in place algorithm, no extra space is needed.
Heapsort has two steps:
- first make a max heap (or min heap), this operation takes O(N)
- pop the root of the heap, swap it with the last element in the heap (the last leaf), do heapify on the elements rangeing from 1 to N-1. Basically, we build a new max (min) heap on the elements rangeing from 1 to N-1
- repeat the step 2
Checkout other sorting programs here.....
ReplyDeleteHeap Sort in C
Bubble Sort in C
Insertion Sort in C
Selection Sort in C
Quick Sort in C