10 ms·

Visualizing and exploring sorting algorithms in two dimensions

74 points by thesephist 7y ago

mrami 7y ago
Selection sort and insertion sort are not O(n) algorithms...
- thethirdone 7y ago
  If swaps are the only thing you are counting, selection sort is O(n). I can't come up with a reasonable way to consider insertion sort O(n) though.
  - klyrs 7y ago
    The article describes these algorithms "efficient" on the basis of being linear, and they're not. Insertion and selection require O(n^2) moves or compares respectively (or, n log(n) with use of data structures). As it stands, the page is pretty as heck but teaching a misconception.
    - thethirdone 7y ago
      > The article describes these algorithms "efficient" on the basis of being linear, and they're not. If memory writes are expensive (relative to reads and comparisons), selection sort is much better than insertion and bubble sort. Which is not something I had considered before trying to defend the post from the original comment. > Insertion and selection require O(n^2) moves or compares respectively (or, n log(n) with use of data structures). As it stands, the page is pretty as heck but teaching a misconception. I am definitely aware of the runtime of the sorting algorithms discussed. I have written about all of them [0]. Originally, I was going to agree and write about how it was a concerning misconception, but at least in the case of selection sort there is some (albeit small) merit to considering selection sort as O(n). Though given that I cannot come up with a defense for insertion sort it is likely the author doesn't understand the time complexity of the sorting algorithms presented. [0]: http://thethirdone.github.io/blog/posts/random-sorting/ http://thethirdone.github.io/blog/posts/random-sorting/
      - devin 7y ago
        Great article. Thanks for posting.
  - mrami 7y ago
    > If swaps are the only thing you are counting, selection sort is O(n). And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm." [1] We shouldn't be confusing people that actually want to learn about this stuff. [1] https://en.wikipedia.org/wiki/Time_complexity https://en.wikipedia.org/wiki/Time_complexity
    - thethirdone 7y ago
      > And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) That is an excellent phrase. > We shouldn't be confusing people that actually want to learn about this stuff. I definitely agree that Selection sort should definitely not be described as O(n) to beginners. I was just pointing out a subtly. In the strange case where memory writes are much more expensive than reads or comparisons, it is correct to say the Selection sort takes O(n) time.
      - mrami 7y ago
        I'm not sure what conditions you have in mind, but in the selection sort, the comparisons are O(n^2), and the assignments are O(n). If comparisons are a fixed, non-zero cost, and assignments are a fixed, non-zero cost, then the comparisons in your selection sort will always overwhelm the assignments, and I can tell you at exactly which input size. https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a7d5 https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a...
    - ivanhoe 7y ago
      > And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) Good one, but you probably meant Satyr (or Faun as Romans called it)
      - mrami 7y ago
        Centaurs are multifaceted and live rich, complex inner lives. https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/media/File:Achilleus_Lyra.jpg https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/...
- FabHK 7y ago
  Yes. What sort of reasoning is that? I can present the result in a square picture, thus it's O(n)... The point is that creating each row of the picture does not take constant time; a longer row will take more time to create. Both selection sort and insertion sort are O(n^2). Sorting by pairwise comparison is O(n log n) at best.
thethirdone 7y ago
> Most languages’ baseline sort operations implement quicksort under the hood, including the standard C library’s gsort() and JavaScript’s Array.prototype.sort() There isn't any "JavaScript's Array.prototype.sort()". Different implementations use different algorithms. I know V8 used to use Quicksort with insertion sort for (sub)arrays smaller than 10 elements (the implementaion has changed since I last looked, but I don't know what). But SpiderMonkey has and still does use a bottom up mergesort with insertion sort for subarrays of length 3.
- thethirdone 7y ago
  A cursory look at the V8 source seems to show that it delegates sorting to std::sort which in libstdc++ (gcc) is Introsort (a hybrid Quicksort + Heapsort).
  - Leszek 7y ago
    A more detailed look will show that it uses Timsort: https://cs.chromium.org/chromium/src/v8/third_party/v8/builtins/array-sort.tq https://cs.chromium.org/chromium/src/v8/third_party/v8/built...
    - thethirdone 7y ago
      Well I don't know how someone not used to the code was suppose to find it at that odd location. Thanks for showing me where its actually implemented.
      - Leszek 7y ago
        Yeah, for someone not used to the code it's tough. The "insider knowledge" is that builtins defined in .tq files (files compiled by the Torque compiler[0]) are added to entries in the Builtins enum, which itself is defined as a giant macro[1] that pulls in a Torque generated macro[2]. In the bootstraper (which sets up the standard library), the Builtins::kArrayPrototypeSort builtin is installed as "sort" onto Array.prototype[3], which means you should grep for "ArrayPrototypeSort", which is defined in the linked .tq file. [0] https://v8.dev/docs/torque https://v8.dev/docs/torque [1] https://cs.chromium.org/chromium/src/v8/src/builtins/builtins-definitions.h https://cs.chromium.org/chromium/src/v8/src/builtins/builtin... [2] https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque-generated/builtin-definitions-tq.h https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque... [3] https://cs.chromium.org/chromium/src/v8/src/init/bootstrapper.cc?l=1687&rcl=6d7e1dd21b6495d3b55afae266edb65b41c40b20 https://cs.chromium.org/chromium/src/v8/src/init/bootstrappe...
rwnspace 7y ago
Is it just me, shoe-horning this in there, or does this picture [1] of the Quicksort remind anyone else of a Scutoid? [2] [1] https://dotink.co/img/quick-color.png https://dotink.co/img/quick-color.png [2] https://en.wikipedia.org/wiki/Scutoid https://en.wikipedia.org/wiki/Scutoid
sorokod 7y ago
> Quicksort is a mouthful to explain in detail Don't know about that, this is not efficent but "explains" quicksort in general: fun <T : Comparable<T>> quickSort(list: List<T>): List<T> = with(list) { if (size < 2) this else { val pivot = first() val (smaller, greater) = drop(1).partition { it <= pivot } quickSort(smaller) + pivot + quickSort(greater) } }

74 points by thesephist 7y ago

mrami 7y ago

Selection sort and insertion sort are not O(n) algorithms...

thethirdone 7y ago
If swaps are the only thing you are counting, selection sort is O(n). I can't come up with a reasonable way to consider insertion sort O(n) though.
- klyrs 7y ago
  The article describes these algorithms "efficient" on the basis of being linear, and they're not. Insertion and selection require O(n^2) moves or compares respectively (or, n log(n) with use of data structures). As it stands, the page is pretty as heck but teaching a misconception.
  - thethirdone 7y ago
    > The article describes these algorithms "efficient" on the basis of being linear, and they're not. If memory writes are expensive (relative to reads and comparisons), selection sort is much better than insertion and bubble sort. Which is not something I had considered before trying to defend the post from the original comment. > Insertion and selection require O(n^2) moves or compares respectively (or, n log(n) with use of data structures). As it stands, the page is pretty as heck but teaching a misconception. I am definitely aware of the runtime of the sorting algorithms discussed. I have written about all of them [0]. Originally, I was going to agree and write about how it was a concerning misconception, but at least in the case of selection sort there is some (albeit small) merit to considering selection sort as O(n). Though given that I cannot come up with a defense for insertion sort it is likely the author doesn't understand the time complexity of the sorting algorithms presented. [0]: http://thethirdone.github.io/blog/posts/random-sorting/ http://thethirdone.github.io/blog/posts/random-sorting/
    - devin 7y ago
      Great article. Thanks for posting.
- mrami 7y ago
  > If swaps are the only thing you are counting, selection sort is O(n). And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm." [1] We shouldn't be confusing people that actually want to learn about this stuff. [1] https://en.wikipedia.org/wiki/Time_complexity https://en.wikipedia.org/wiki/Time_complexity
  - thethirdone 7y ago
    > And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) That is an excellent phrase. > We shouldn't be confusing people that actually want to learn about this stuff. I definitely agree that Selection sort should definitely not be described as O(n) to beginners. I was just pointing out a subtly. In the strange case where memory writes are much more expensive than reads or comparisons, it is correct to say the Selection sort takes O(n) time.
    - mrami 7y ago
      I'm not sure what conditions you have in mind, but in the selection sort, the comparisons are O(n^2), and the assignments are O(n). If comparisons are a fixed, non-zero cost, and assignments are a fixed, non-zero cost, then the comparisons in your selection sort will always overwhelm the assignments, and I can tell you at exactly which input size. https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a7d5 https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a...
  - ivanhoe 7y ago
    > And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) Good one, but you probably meant Satyr (or Faun as Romans called it)
    - mrami 7y ago
      Centaurs are multifaceted and live rich, complex inner lives. https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/media/File:Achilleus_Lyra.jpg https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/...
FabHK 7y ago
Yes. What sort of reasoning is that? I can present the result in a square picture, thus it's O(n)... The point is that creating each row of the picture does not take constant time; a longer row will take more time to create. Both selection sort and insertion sort are O(n^2). Sorting by pairwise comparison is O(n log n) at best.

thethirdone 7y ago

> Most languages’ baseline sort operations implement quicksort under the hood, including the standard C library’s gsort() and JavaScript’s Array.prototype.sort() There isn't any "JavaScript's Array.prototype.sort()". Different implementations use different algorithms. I know V8 used to use Quicksort with insertion sort for (sub)arrays smaller than 10 elements (the implementaion has changed since I last looked, but I don't know what). But SpiderMonkey has and still does use a bottom up mergesort with insertion sort for subarrays of length 3.

thethirdone 7y ago
A cursory look at the V8 source seems to show that it delegates sorting to std::sort which in libstdc++ (gcc) is Introsort (a hybrid Quicksort + Heapsort).
- Leszek 7y ago
  A more detailed look will show that it uses Timsort: https://cs.chromium.org/chromium/src/v8/third_party/v8/builtins/array-sort.tq https://cs.chromium.org/chromium/src/v8/third_party/v8/built...
  - thethirdone 7y ago
    Well I don't know how someone not used to the code was suppose to find it at that odd location. Thanks for showing me where its actually implemented.
    - Leszek 7y ago
      Yeah, for someone not used to the code it's tough. The "insider knowledge" is that builtins defined in .tq files (files compiled by the Torque compiler[0]) are added to entries in the Builtins enum, which itself is defined as a giant macro[1] that pulls in a Torque generated macro[2]. In the bootstraper (which sets up the standard library), the Builtins::kArrayPrototypeSort builtin is installed as "sort" onto Array.prototype[3], which means you should grep for "ArrayPrototypeSort", which is defined in the linked .tq file. [0] https://v8.dev/docs/torque https://v8.dev/docs/torque [1] https://cs.chromium.org/chromium/src/v8/src/builtins/builtins-definitions.h https://cs.chromium.org/chromium/src/v8/src/builtins/builtin... [2] https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque-generated/builtin-definitions-tq.h https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque... [3] https://cs.chromium.org/chromium/src/v8/src/init/bootstrapper.cc?l=1687&rcl=6d7e1dd21b6495d3b55afae266edb65b41c40b20 https://cs.chromium.org/chromium/src/v8/src/init/bootstrappe...

rwnspace 7y ago

Is it just me, shoe-horning this in there, or does this picture [1] of the Quicksort remind anyone else of a Scutoid? [2] [1] https://dotink.co/img/quick-color.png https://dotink.co/img/quick-color.png [2] https://en.wikipedia.org/wiki/Scutoid https://en.wikipedia.org/wiki/Scutoid

sorokod 7y ago

> Quicksort is a mouthful to explain in detail Don't know about that, this is not efficent but "explains" quicksort in general: fun <T : Comparable<T>> quickSort(list: List<T>): List<T> = with(list) { if (size < 2) this else { val pivot = first() val (smaller, greater) = drop(1).partition { it <= pivot } quickSort(smaller) + pivot + quickSort(greater) } }