Sorting questions?

heap, sorting

Solution

I don't think `HeapSort` is considered "Divide and Conquer", because in no moment the algorithm sub-divides the problem into sub-problems. To do HeapSort the algorithm Executes `ExtractMin` or `ExtractMax` until the Heap is empty. These actions are `O(logn)` because after each `ExtractMin` or `ExtractMax` the `Heap` has to do `Heapify` to mantain the partial-order of it. At the end has a cost of `O(nlogn)` because it does `n` `ExtractMin` or `ExtractMax`.

Here is a pseudo-code

HeapSort()
 heap
 new_ ordered_collection
 while(heap.NotEmpty)
   new_ ordered_collection.add(heap.ExtractMin)//or ExtractMax
   heap.Heapify //could be MaxHeapify or MinHeapify
 return new_ ordered_collection

Notice that `ExtractMin` and `ExtractMax` pops out the minimum or the maximum element of the Heap.

As you can see, i don't see the "Divide and Conquer" strategy.

But the `heap.Heapify` reorder the elements based on the partial order of the heap. This one defines the relationship between each node and his two child, because of this, `heap.Heapify` applies a "Divide and Conquer" strategy, but that is a thing of the DataStructre itself no of the algorithm.

And bubble sort is a `naive` algorithm.

Problem

Is a heap sort considered a "divide and conquer" sort or a priority queue sort? Also, what category of sort would a bubble sort fit into (other than horrible). I've read that a heap sort is generally considered a "divide and conquer" sort, but it can be a priority queue sort. Is it strictly one or the other? Or is it some how both? I cannot find anything on what a bubble sort may be considered.

Original source