21–30 of 39 posts
I wish it had a "pathological case" option for data to sort per-algorithm. In particular: Quicksort, which (unless you're willing to make an (expensive) call to a (P)RNG per iteration) has a worst case of O(n^(2)) time.
I wish it had a "pathological case" option for data to sort per-algorithm. In particular: Quicksort, which (unless you're willing to make an (expensive) call to a (P)RNG per iteration) has a worst case of O(n^(2)) time.
Why would the worst case change if you use a random number for choosing the pivot?
Technically, the worst case stays the same.
In actuality, the worst case occurring via random chance is not a problem, as it occurs vanishingly infrequently. The problem is malicious input.
I wish it had a "pathological case" option for data to sort per-algorithm. In particular: Quicksort, which (unless you're willing to make an (expensive) call to a (P)RNG per iteration) has a worst case of O(n^(2)) time.
Despite that no real-world quicksort implementations have that worst case (due to fallbacks to other sorts), it seems like it's useful to see the pathological case of pure quicksort anyway.
Thread Hijack: A little while ago there was a link on HN to a visual explanation of text compression, but I do not remember the compression format. It was the first time I ever understood how text compression works. There was a paragraph of text and the author stepped through the compression of the paragraph with an accompanying depiction of the original paragraph. Does this sound familiar to anyone? It was the first…
Thread Hijack: A little while ago there was a link on HN to a visual explanation of text compression, but I do not remember the compression format. It was the first time I ever understood how text compression works. There was a paragraph of text and the author stepped through the compression of the paragraph with an accompanying depiction of the original paragraph. Does this sound familiar to anyone? It was the first…
http://jvns.ca/blog/2013/10/24/day-16-gzip-plus-poetry-equal...
The good stuff is here: http://www.infinitepartitions.com/art001.html
I'm really partial to this site for visualizing: http://www.cs.usfca.edu/~galles/visualization/Algorithms.htm...
Earlier quoted context omitted.
Despite that no real-world quicksort implementations have that worst case (due to fallbacks to other sorts), it seems like it's useful to see the pathological case of pure quicksort anyway.
At which case: why bother using quicksort?
Earlier quoted context omitted.
At which case: why bother using quicksort?
It's simple(relatively) and almost always quite fast. Or would you rather use slowsort?
And merge sort is often faster, especially if the comparison function is relatively expensive.
Another nice sort visualization is Sortviz.org. For example:
http://sortvis.org/algorithms/combsort.html
and
Earlier quoted context omitted.
It's simple(relatively) and almost always quite fast. Or would you rather use slowsort?
Quicksort is not simple if you have to build in an entire other sorting algorithm as a failsafe. And merge sort is often faster, especially if the comparison function is relatively expensive.