4 ms·

Thanks. Yes, I didn't mean that shaker sort is good for speed, just interesting for the approach. Also, bubble sort, though one of the slowest, has this proper

by vram22 8y ago

Thanks. Yes, I didn't mean that shaker sort is good for speed, just interesting for the approach. Also, bubble sort, though one of the slowest, has this property: https://en.wikipedia.org/wiki/Bubble_sort#Use https://en.wikipedia.org/wiki/Bubble_sort#Use [ In computer graphics bubble sort is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). ]

kragen 8y ago
Insertion sort has that capability too, without bubble sort's drawbacks.
- vram22 8y ago
  Interesting, didn't know. Will look again at its Wikipedia page. Had looked recently, may not have noticed that. Apropos of insertion sort, I think I read (it was years ago) in the Jon Bentley book (which I think I mentioned upthread), called Writing Efficient Programs, that he said insertion sort is used by some people in quicksort, as the alternative algorithm, when the sizes of the subarrays remaining to be sorted (recursively) are down a small size, in which case insertion sort has less overhead than quicksort, so is faster for those small chunks. (Or it could have been selection sort (instead of insertion sort.) In other words, a hybrid sort algorithm.
  - nwallin 8y ago
    It's actually slightly cleverer than that. When quicksort recurses into a subarray that is less than the critical size, (call it k) it does not switch to a simpler O(n^2) sort: it simply returns, leaving the subarray unsorted. The result is that the final array is mostly sorted, where no element is more than k distance from its true position. Once the array is mostly sorted, it then runs insertion sort, which is fast on mostly sorted arrays. Despite the fact that in the general case insertion sort is O(n^2), it is O(nk) on this mostly sorted array. Selection sort performs no better on mostly sorted arrays than insertion sort. Which is why insertion sort is used instead of selection sort.
    - vram22 8y ago
      Wow, that is clever. Not doing more than you need to - for the same effect - kind of thing. Thanks for sharing. I've been playing around with various simple algorithms for different tasks, over a period, and been noticing that there is a lot of scope for improving efficiency, even if by small amounts, sometimes by a bit more, by making various tweaks to the logic, often including early termination techniques. A well-known example of early termination is: to find if a number n is prime, instead of checking whether it is divisible by all the integers from 2 to n - 1, you can just check for those up to the square root of n. (There are more optimizations on those lines possible, of course.) I've found that there can be many quick wins in this area, often in various algorithms that process arrays. For example, problems involving arrays on Rosetta Code.

by vram22 8y ago

kragen 8y ago

Insertion sort has that capability too, without bubble sort's drawbacks.

vram22 8y ago
Interesting, didn't know. Will look again at its Wikipedia page. Had looked recently, may not have noticed that. Apropos of insertion sort, I think I read (it was years ago) in the Jon Bentley book (which I think I mentioned upthread), called Writing Efficient Programs, that he said insertion sort is used by some people in quicksort, as the alternative algorithm, when the sizes of the subarrays remaining to be sorted (recursively) are down a small size, in which case insertion sort has less overhead than quicksort, so is faster for those small chunks. (Or it could have been selection sort (instead of insertion sort.) In other words, a hybrid sort algorithm.
- nwallin 8y ago
  It's actually slightly cleverer than that. When quicksort recurses into a subarray that is less than the critical size, (call it k) it does not switch to a simpler O(n^2) sort: it simply returns, leaving the subarray unsorted. The result is that the final array is mostly sorted, where no element is more than k distance from its true position. Once the array is mostly sorted, it then runs insertion sort, which is fast on mostly sorted arrays. Despite the fact that in the general case insertion sort is O(n^2), it is O(nk) on this mostly sorted array. Selection sort performs no better on mostly sorted arrays than insertion sort. Which is why insertion sort is used instead of selection sort.
  - vram22 8y ago
    Wow, that is clever. Not doing more than you need to - for the same effect - kind of thing. Thanks for sharing. I've been playing around with various simple algorithms for different tasks, over a period, and been noticing that there is a lot of scope for improving efficiency, even if by small amounts, sometimes by a bit more, by making various tweaks to the logic, often including early termination techniques. A well-known example of early termination is: to find if a number n is prime, instead of checking whether it is divisible by all the integers from 2 to n - 1, you can just check for those up to the square root of n. (There are more optimizations on those lines possible, of course.) I've found that there can be many quick wins in this area, often in various algorithms that process arrays. For example, problems involving arrays on Rosetta Code.