kuroshivo
kuroshivo
Joined: Jun 8, 2019
  • Threads: 2
  • Posts: 11
May 14th, 2021 at 7:49:43 AM permalink
Quote: ThatDonGuy

The use of heap sort in the title leads me to ask: is heap sort still the fastest method?



Well, after reading Donald Knuth's "The Art of Computer Programming" volume 3 on sorting and searching (more than 10 years ago) I have the feeling that there is no one-size-fits-all answer. I think there are some shallow discussions on Wikipedia, but the actual meat is in Knuth's TAOCP.
EdCollins
EdCollins
Joined: Oct 21, 2011
  • Threads: 19
  • Posts: 1553
May 14th, 2021 at 8:39:17 AM permalink
I remember, a bit more than 22 years ago, I first became absolutely fascinated by all of the different sorting algorithms that were available. Heap Sort, Insertion Sort, Bubble Sort, Quicksort, Shell Sort, Merge Sort, etc., etc., etc.

There are many different websites that help to visualize how each algorithm works. Here's just one of many:

https://www.toptal.com/developers/sorting-algorithms

And yes, there is no one size fits all answer as to which algorithm is best/fastest. A lot of it has to do with what your data looks like before it is sorted. Is it completely random? Is it nearly sorted already? Is it completely reversed? Etc.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 109
  • Posts: 5369
May 14th, 2021 at 10:07:42 AM permalink
Quote: kuroshivo

Well, after reading Donald Knuth's "The Art of Computer Programming" volume 3 on sorting and searching (more than 10 years ago) I have the feeling that there is no one-size-fits-all answer. I think there are some shallow discussions on Wikipedia, but the actual meat is in Knuth's TAOCP.


Speaking of Knuth, Volume 4a has a few pages on generating permutations, which was the original question in this post - so of course it's back at my office while I have been teleworking for over a year now.
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 42
  • Posts: 2352
May 15th, 2021 at 7:45:29 AM permalink
Quote: ThatDonGuy

The use of heap sort in the title leads me to ask: is heap sort still the fastest method? 40 years ago, it was, but I have done some comparisons since then, and I have found that, with the vast increases in processing speed, quicksort seems to be faster now. (Well, what I call "quicksort-N", where N is usually 8 or 9; if there are N or more values in the current comparison, do a quicksort, but if there are fewer, do a "wimpysort" like bubble or shaker.)

Bin sort would be even faster for this problem. Just create an incidence array of size 10 and count how many of each digit. It works for arbitrarily long sequences, whereas the prime algorithm will quickly exceed the max data size. Heap sort is O(n log n). Bin sort is O(n).
End of the world website: www.climatecasino.net

  • Jump to: