What should the proper name for the QuickSort algorithm be?

[swampwiz]

OK, I understand the deal - it was the (and seems to still be) the fastest algorithm for sorting a random set (although it can break down to O(n²) for the worst case non-random.) But it seems that it should have a name that describes its essence, like MergeSort or InsertionSort.

The essence of QuickSort is to find a pair of elements (from each side) that should be on the other side due to their comparison with the pivot value, and then swap them, thus guaranteeing that when the set is divided, the elements of one subset are always less than the elements of the other set (i.e., the conquering.) It seems to me that although most (all?) sort algorithms do swaps, rather than swapping between adjacent elements, or between one constant index element and that of another index, QuickSort does swaps all over the place. Thus, if I had to name QuickSort, I think I would name it SwapSort.

What do you think?

 

[MisterX]

No, please call it quicksort.

As for your observations that most sorts seem to use swaps, swaps are a feature of a number in-place algorithms. One might have a sorting algorithm that is not in-place. In this case, a sorted copy of the data might be made in a second data structure. A disadvantage of this is that it requires the extra memory for the second data structure.

Also, a sorting algorithm might perform an operation like shifting a bunch of elements by 1 position in the sequence, and this might be not be exactly the same as swapping things.

 

[jim mcnamara]

C A R Hoare first developed the QuickSort in 1960. Way back, some people used to use his name to refer to the QuickSort algorithm, Hoare's QuickSort.