Видео

Dumb partents think this stupid measure is gonna work.

sorry I would tell you but arras removed the entire functionality to make these servers 😭

Yea,quicksort looks way different from this,this is probably some sort of random sort that i dont know about…

Okay,i think this is quicksort but with left and left pointers,no right pointers…

@@duothehybrid 💀

thx, if you have any suggestions please comment them bc I have no more ideas to add

@@bitonic589 your videos have inspired me to start a simple visualisation using C++/SDL on my own LSD-256-radix sort implementation! I will comment again if I get any new ideas not already covered. The important line of my radix sort that avoids modulo divisions, and also avoids bit shifts and logical ands is: for ( auto i : input ) { count[ *((uint8_t*)&i + pass) ]++; } Where pass is the least significant byte as the radix. All good fun (as long as machine little endian lol )

@@bitonic589 I just remembered I do have an idea! For the last 10 years or so we have lived in a world where CPU clocks didn't get much faster, but number of processing cores has increased instead. Therefore it might be interesting to try to make some multi threaded sorts to take advantage of all this extra processing power? I appreciate it might not change the visualizations much.

@@paulchamberlain7942 Yes, I have tried this. You can scroll to the bottom to try Parallel merge sort. It utilizes multiple threads to merge multiple subsections at once. However, it is very laggy and I currently can't find any way to fix it, I assume it may just be that an internet browser can only go so far in using CPU resources. Great suggestion though

@@Plaer1 ? No, this is common. Real data is often partially sorted in some way, whether that be in ascending or descending order. Quick sort is unreliable, only good for unrealistically random data. It's best to use a hybrid sort like timsort or grailsort

@@bitonic589 real data being sorted backwards isnt very common...but sure

Most developers use introsort also known as std::sort,i think,idk

@@soosboi Yes

@@Ghal00xx what

@@bitonic589i heard you made vids about sorting algorithms before and I made one myself :)

@@ForlornFraudFacade Ok so you make sorted sections of two by compare and swap and then shellsort them with ²exponential gaps

@@bitonic589ok thank

@@bitonic589stability:

@@maymaymhm no 👍

Indeed no ​@bitonic589

idk lol it glitched

??

@@rka3477 nope different algorithm

idk they forgot to stop moving

@@Mini-Rusty Idk nobody likes coding channels

Shell proposed this algorithm, with these gaps, in 1959. By 1960, improved gap sequences which avoided precisely this problem were already being proposed - Papernov, Hibbard, etc. Basically, one must avoid a pure geometric sequence with integer base, and these early proposals (up to the early 1980s) were normally for an integer geometric sequence that was offset by a constant; for example, Hibbard's sequence is just the Mersenne numbers, 2^k-1. This includes Knuth's recommendation from the 1970s: (3^k+1)/2, no greater than N/3. Pratt proved that Shell's original sequence had worst-case complexity O(N^2), and that these conventional alternatives were O(N^3/2) worst-case. In 1971 he showed that using the 3-smooth numbers (2^p * 3^q) reduced the asymptotic complexity to O(N log^2 N). However, because this involves a large number of passes over the data, the average-case performance of this version is significantly worse than the conventional sequences. It's still an interesting way to construct a sorting network that has O(log^2 N) layers, so this is still vaguely relevant to parallel computing (eg. on GPUs). The next advance was by Sedgewick, who showed that the sum of two near-geometric sequences yielded better results, both asymptotically and in practice, than a single one as previously used. One such sequence is hilariously easy to compute: start with a=(4 << 2*k) and b=(3 << k), then at each iteration, take gap=a+b+1, then shift a right by 2 and b right by 1. The final entries in this sequence are 8, 3, 1 as the significant bits of a and b are shifted into oblivion. Sedgewick sequences have worst-case O(N^4/3) complexity, which is practically useful up to the millions or even low billions of elements. Most other sequences have been designed for average-case performance, without being formally analysed for worst-case performance. Finding killer inputs for them is quite difficult, though, which suggests that they are robust in practice.

@Kromaatikse I made my own sequence which is approx n log n (improved version of sedgewick)

In-place radix sort

lol 💀 just try it

sry I couldnt find a way to fix the sound but im working on a new one which will have better sound

@@TNTSuperMan did you even watch the video

I'm afraid TNTSuperMan is correct. In this case, it looks like the implementation of this Quick has a pivot that is found in a non-random assignment with no comparisons. It is tough to use a system like this since from the left, from the right, or even exactly in the center (with a special input), there is a way for the pivot to not guarantee any additional items in the partition it creates. I am going to guess that this implementation uses an LR pointer partition scheme with a left or right pivot. When it tries to sort, sometimes, either end of the partition scheme would only result in the left pivot being the least or the right pivot being the greatest item. However, the sort doesn't know that until it tries and finds nothing. This is considered a single scan. Abusing the weaknesses of algorithms that have weak strategies is not that difficult. A reversed array tends to kill algorithms that rely on there being some sortedness amidst the unsortedness in the array, which Quicksorts with a left or right pivot traditionally rely on. However, on a reversed array, no sortedness exists. Thus, nothing less than or greater than the pivot, and the algorithm scans a subset of the N items O(N) times, and N * O(N) = O(N^2).

@@PCBoyStudios Bro chill 💀 The title was "Sometimes it isn't" not that it's always slow. Anyways, this implementation uses a classic Lomuto Partition, implementing the standard quicksort. If you look at the quicksort algorithm, you will see my implementation is the standard. The point of the video though, was to show quick sort's weakness, and how in some cases, it is not a reliable algorithm like merge sort or heap sort is.

@@bitonic589 Nope, I just know common sorting algorithms all too well that I can analyze what made it do that.

@@PCBoyStudios Well usually quicksort uses a Lomuto partition, and that's what's used here. You can check out my new sort visualizer if you want, it has dual pivot partitions and random partitions

It's just water 😭

Link

@@AngelinSofya well the link for the one in the video is infinitesites.glitch.me/sortvisualizer.html but that's an old one, I made a newer one which is much better: svis4.glitch.me/