Re:Sorting algorithms visualizer
by phunehehe0 on Friday May 27, 2016 @10:38AM
(#11786315)
I went through the list of algorithms in Wikipedia [0] and a reader pointed out that block sort [1] is an interesting case. It has all the best properties listed, except the worst case swaps, which I can't find in Wikipedia.
[0]: https://phunehehe.net/best-sorting-algorithm/ [1]: https://en.wikipedia.org/wiki/Block_sort
Re:Sorting algorithms visualizer
by nightcracker on Friday May 27, 2016 @02:37AM
(#11784306)
Most of these are possible to combine (see for example https://github.com/BonzaiThePenguin/WikiSort), but I feel that this subset is impossible together:
- Operates in place, requiring O(1) extra space.
- Worst-case O(n·lg(n)) key comparisons.
- Worst-case O(n) swaps.
Re:Sorting algorithms visualizer
by alejohausner on Friday May 27, 2016 @02:37PM
(#11787968)
Well, spaghetti sort runs in linear time: O(n) time is spent setting up the device, and O(n) reading out the result. The actual sorting step is O(1) !!!
Unfortunately, it's limited to sorting numbers, and uses O(n) additional space (to be precise, it uses O(n) additional volume).
- Stable: Equal keys aren't reordered.
- Operates in place, requiring O(1) extra space.
- Worst-case O(n·lg(n)) key comparisons.
- Worst-case O(n) swaps.
- Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.
There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application."
Is there any formal proof that such an algorithm doesn't exist? Are some of those criterion mutually exclusive?