- #1
swampwiz
- 571
- 83
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(n2) 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?
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?