What should the proper name for the QuickSort algorithm be?

  • Thread starter swampwiz
  • Start date
  • #1
300
11

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
760
69
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:
  • #3
jim mcnamara
Mentor
3,949
2,351
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.
 

Related Threads on What should the proper name for the QuickSort algorithm be?

Replies
16
Views
3K
Replies
4
Views
549
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
9K
Replies
13
Views
6K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
3K
Replies
11
Views
697
Replies
6
Views
1K
Top