ANONYMOUS wrote:
> Hi! I just had a discussion with a friend over Quicksort algorithm and we were confused as to which sort type quicksort is. In the lecture Gozz mentioned it was Distribution sort however when searching online it mentions it is comparison sort. The part I'm confused about is in the slides it is stated that distribution sort "Distribute the elements o the list into multiple intermediate data structures (blocks) such that there are no inversion between blocks", which is what Quicksort does but doesn't quicksort first use comparisons to get the 2 "blocks" (i.e. less than pivot or more than pivot). Could a sorting algorithm be both comparison-based and distribution-based?
>
> Could someone clarify which one it is and why it is that type? Thank you very much for reading and helping!
These are not exclusive categories. Indeed, as you say, quicksort is both.
Comparison-based sorting algorithms are restricted to only be able to compare elements, and have no other way to get information about their ordering. Quicksort only requires comparison, so it is a comparison-based sorting algorithm.
Distribution sorting algorithms, as you quoted, work by distributing the elements into blocks such that there are no inversions between blocks, and then sorting within each block if necessary. By this definition quicksort can be interpreted as a distribution sort, but it only has two blocks since by comparing each element to the pivot it only gets one bit of information, and can only distinguish between elements <= pivot and > pivot.
I am not interested in these categories for the purposes of memorizing a complete taxonomy of all algorithms. They are of interest because understanding the ways in which the logic of different algorithms is similar helps understand the logic itself. We derived quicksort without having any concept of what a distribution sort was, but we are able to generalize the concept and use it to reason about quicksort, bucket sort, counting sort, etc. So long as you are able to understand and work with the concepts and the logic, it is not particularly meaningful whether quicksort is classified as a distribution sort. I would be more interested in your ability to, given some sorting algorithm, formulate an argument for why it should or should not be considered a distribution sort, or otherwise compare the properties and logic of the algorithms.
As an exercise in exactly that, here are a couple of fun open-ended questions to have a think about:
1. Do you believe heap sort is a distribution sort? What is your argument to support your position? Can you formulate a counterargument?
2. Could you adapt merge sort to use more information than just comparison? If so, how does your resulting algorithm relate to others we have covered in lectures (what is it similar to, etc.)?
Cheers,
Gozz
