Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What should the proper name for the QuickSort algorithm be?

  1. May 27, 2013 #1
    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?
     
  2. jcsd
  3. May 27, 2013 #2
    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.
     
    Last edited: May 27, 2013
  4. May 27, 2013 #3

    jim mcnamara

    User Avatar

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What should the proper name for the QuickSort algorithm be?
  1. Quicksort comparison (Replies: 1)

Loading...