Sorting questions?

Question

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.

Answer 1

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.

Answer 2

Heap sort has the time complexity of a 'divide and conquer' algorithm (such as quick sort), but it does not behave like a divide and conquer algorithm.

Because it splits the data into a 'sorted' section and an 'unsorted' section, it is really a kind of selection sort. It takes advantage of the heap data structure to more efficiently select the minimum element from the unsorted list at each step. I suppose you could say it is a 'priority queue sort' because of this, but it should be mentioned that the entire operation can be done in-place rather than building a separate heap.

Heap sort is typically outperformed by quicksort, except that quicksort has a worst-case complexity of O(N^2) (versus heap sort's worst case of O(N.logN)).

Bubble sort is also an in-place algorithm, but it is considered 'naive'.