Some say BogoSort is still drinking beer halfway the first race.

@joshuagetusername4779

3 жыл бұрын

11 factorial isn't that big yet, compared to 200k squared. So BogoSort would probably have finished the first race by now, but it will not have made any progress with the second race.

@kitalthevali

3 жыл бұрын

@@joshuagetusername4779 bogo sort just randomizes the list and checks if it is sorted so there is a chance for that one-hit k.o. on really large lists

@bastian_5975

3 жыл бұрын

nah, it got lucky and sorted every list first try...

@theonetem

2 жыл бұрын

@@bastian_5975 This is why best case Bogosort has a big O notation of O(1)

@bastian_5975

2 жыл бұрын

@@theonetem well, that's also when you have infinite time. In fact, I'm pretty sure that the best time is actually O(N), because it still has to check if the list is ordered by iterating through the list. So somewhere in the multiverse, bogosort is the best sorting algorithm because it always orders all lists correctly the very first time, so only takes the number of operation to shuffle and then check the list once.

A funny analogy for the radix sort: Imagine you're allowed to bring a car that can drive at half the speed of light to your footrace, but only allowed to drive it on a road. And the bad news is that the track isn't a road. So you have to wait for the road to get built by your road building team, get your tires checked, get your suit ordered, and wait for the asphalt to dry and get painted. And you'd have to spend all those days and weeks and months waiting for all that to happen before you even start the race. And after all that, you're driving a distance you could easily walk in twenty minutes. The difference becomes if you had to walk to mars and back instead. Yeah, you're going to have to wait even longer to build that road, but not by much, and it's astronomically faster to travel half the speed of light there and back

@proloycodes

2 жыл бұрын

the best analogy of radix sort i have ever read

@TigerYoshiki

2 жыл бұрын

That was actually very helpful!

@dale116dot7

Жыл бұрын

Though it works pretty well when you trip and drop your FORTRAN source deck.

@Qualicabyss

11 ай бұрын

Saying you have to wait for the car to be built probably makes more sense but still

Man I've never been so excited to watch sorting algorithm before

@corrucyst

3 жыл бұрын

speak for yourself buddy i am ecstatic to see any sorting algorithm

@simonmultiverse6349

2 жыл бұрын

Heapsort is very good.

The only reason why Radix sort done so well on the last two tests is because it sat around on it's ass the whole first race, so it had energy to spare! Yellow was tired out after the first race. :P

@WhatsACreel

4 жыл бұрын

Hahaha, this is awesome!

@ianosgnatiuc

2 жыл бұрын

The only reason is that it had enoght memory.

@shiinondogewalker2809

10 ай бұрын

@@ianosgnatiuc the only reason is that the pc was powered on during the test

BS! Faster sorting algo is the Stalin Algorithm: - traverse the array - any element that's not ordered gets deleted Courtesy of r/programmerHumor

@WhatsACreel

4 жыл бұрын

Haha, this is great!

@OlavLadnav

3 жыл бұрын

@Santiago Rodriguez Newton Starting with index 0, if the next element is not greater than the previous it gets removed until the element that is greater is met

@programaths

3 жыл бұрын

Sleep sort is better than o(n), it's o(1): www.geeksforgeeks.org/sleep-sort-king-laziness-sorting-sleeping/

@pitri_hub

3 жыл бұрын

@@programaths Yeah, no. It's definitely not in O(1). In most cases, the runtime is depending on the actual values, not the size of the data. The thing is, the sleep "overhead" will be insignificant at some point, when we increase the elements over and over again. Go on, sleep sort an array with 2 billion entries. if the computer doesn't crash because of the enormous amount of threads, it will probably take longer than the waiting time for the maximum value, because of all the scheduling in the background, which means that it indeed scales with the size of the data. The waiting just masks that for "small" amounts of data. Sleep sort is a good "troll physics" algorithm and an interesting brain twister when you're experiencing the idea for the first time.

@programaths

3 жыл бұрын

@@pitri_hub In vernacular term, it's called a joke :-D

Sorting algorithms that did not qualify: 1. Bogocounting sort: create an array of all possible elements. Select a random index in the array and a random index in the list until the element is found, then put it in the sorted list. 2. Natural selection sort: score the list using a fitness function (such as number of items out of order) then copy it but introduce some random swapping of items. Check a random list. If that list has at least the best score so far, reproduce the list but mutate it. If the list does not have the best score so far, delete the list. The list is considered sorted when it has equal fitness to a sorted list. 3. Adaptation sort: inspired by natural selection sort but trimmed down to improve speed and memory usage. Count the number of inversions in the list. Randomly swap two items and check their immediate neighbors to see if it reduces inversions. If it doesn't, then undo the swap. Repeat until there are no inversions.

Now THIS is Computer Science

@WhatsACreel

4 жыл бұрын

Cheers mate :) Thanks for watching!

@whamer100

3 жыл бұрын

now THIS is podracing

I think testing their performance for already-sorted or already-partially-sorted lists for comparison would be a good idea, as some sorts waste more time than others "re-sorting" sorted data

@nolifeorname5731

3 жыл бұрын

Looking at you, quicksort!

@rubixtheslime

3 жыл бұрын

@@nolifeorname5731 "I don't get it, why does EVERY SINGLE number end up on the left side of the pivot? Well, better keep sorting just in case!"

@Kromaatikse

3 жыл бұрын

@@rubixtheslime This is why Quicksort's performance depends so much on the pivot selection and the partitioning method. You want the median of a random sample (not a deterministic one) for the pivot, and ternary partitioning so you don't fall over when there are runs of equal values. It's also a good idea to switch to a sort that's fast on small lists at deep recursion levels, as pivot selection has some overhead which makes it less efficient; most people use insertion sort, but I have a version that uses Splaysort.

@shubh-kr

3 жыл бұрын

@@nolifeorname5731 🤣

@skiunitwaite1187

2 жыл бұрын

@@Kromaatikse .

I knew purple was bubble sort because it was the only one moving at a constant speed the whole time throughout every race.

i love the idea that an algorithm could be so fast that it does a bunch of extra work in its spare time just cos its bored

Me: Ok 5 hours sleep should be just enough to see me through work tomorrow My brain: But which algorithm is actually fastest overall?!

@1Maklak

3 жыл бұрын

The standard library sort, obviously. You just give it the array, array size and a comparison function and you're done. The compiler and runtime will do the rest :)

Oh come on! You shoud've added BogoSort to the first race and have that competitor "quit" after the first one. Just for the memes.

@TheJas-vr2vr

3 жыл бұрын

After the first round, I assumed pink was bogosort under a different name.

@hardlyb

3 жыл бұрын

One place I worked, we had a competition to come up with bad algorithms, and mine, which we called Trans-Hyper-BogoSort 'won'. The Hyper part is that you take whatever terrible sorting algorithm you have, and run it on a generated list, and then, once it's sorted, go back and compare the original list with your data, to see if they were identical. If not, generate another list and try again. The Trans part is that your random generating method has to be fixed, making it very unlikely to actually generate the initial data set. I just plugged BogoSort in, but even Trans-Hyper-Radix sort would have been worse than any of the other entries in the contest.

@bluesillybeard

3 жыл бұрын

@@hardlyb that is what I call dedication.

@PokeShadow77

3 жыл бұрын

@@TheJas-vr2vr I was thinking it was too. Then when I saw the final race... I was certain.

@arroba349

3 жыл бұрын

bogo just yeets and sort in oneshot

Funny how everyone always includes bubble sort in these things, even though the only advantage it has is sheer simplicity.

@OnEiNsAnEmOtHeRfUcKa

2 жыл бұрын

Bubble Sort is there as the "banana for scale".

@BaddeJimme

2 жыл бұрын

It doesn't even have much of a simplicity advantage. Insertion sort requires roughly the same amount of code, while actually being useful.

@dale116dot7

Жыл бұрын

Though a bubble sort can work if you have a very short list and especially if pointer manipulation and dynamic memory allocation are prohibited by your safety coding rules.

@Lightning_Fox

Жыл бұрын

Selection sort is simple as well (my lack of coding skills wrote one in an hour while half asleep) so I really don’t see bubble sort having any advantages

@shiinondogewalker2809

10 ай бұрын

@@dale116dot7 insertion sort does kind of the same as bubble sort but using fewer comparisons/swaps. selection sort does the same number of comparisons as bubble sort but only one swap per element. Bubble sort 'can' work but it never makes sense to use it

BTW, the sorting algorithm used by the C++ standard library, in both gcc and MSVC, is called introsort. It uses quicksort until it hits a certain recursion depth, at which point it switches to heapsort in order to maintain the required O(n lg n) worst-case behavior. (Otherwise, quicksort can devolve to O(n^2) in some pathological cases.) On sufficiently random data, it is effectively pure quicksort, since it should seldom (if ever) get to a deep enough recursion level to switch over. Given that, it would have been interesting to test with mergesort rather than whatever version of quicksort you found. You could do this by using std::stable_sort, which uses mergesort (or some close variant) in any C++ library I'm aware of.

@odomobo

3 жыл бұрын

And since quicksort is a partitioning algorithm, introsort switches to insertion sort on small partitions. This also explains why blue was a close second on the short arrays -- in that case it's basically just insertion sort with a tiny extra bit of overhead.

I would appreciate comparison of random-sorted data, partially sorted data and reverse sorted data..

@zwz.zdenek

3 жыл бұрын

Unfairly partitioned data and data producing hash collisions would be great fodder for these benchmarks.

11:30 I'm dying here 😂🤣🤣🤣Pink taking the piss out of everyone

@aleksszukovskis2074

3 жыл бұрын

greatest anime plot twist lol

Very nice illustration why hybrid sorting algorithms are so popular where small sublists are sorted with something simpler than the large list.

For me the conclusion is to always use the std sort until you actually know what you're doing. The std works good at every scenario.

@mitlanderson

2 жыл бұрын

So mergesort

@this_commenter_had_a_stroke

Жыл бұрын

@@mitlanderson std sort is quicksort+ heapsort, and it literally just starts using quicksort, and if quicksort takes too long it switches to heapsort.

the disappointment of placing my bets on pink in the first race. i have been shattered

I would give anything for a teacher like you in my school. The idea was great and interesting. Thank you :D

@WhatsACreel

4 жыл бұрын

I'm so happy people find my humble offerings valuable! Cheers for watching mate :)

I was laughing so hard watching the poor bubble sort shambling through the 2nd race - it was pretty obvious who that one was ;)

pink is basically sonic. Slows down to give people a chance, but when it comes to a true challenge goes all out

This video got an "instant subscribe" for me. By far the most interesting algorithm comparison to watch! Amazing job!

Go bubble sort! Time to prove the haters wrong!

@w01dnick

3 жыл бұрын

Never understood why people think bubble sort is simple. To me selection sort is much more natural and easier to implement.

@w01dnick

3 жыл бұрын

Btw, insertion sort is also much more natural than bubble to me. People usually sort cards that way.

@w01dnick

3 жыл бұрын

@@cortexauth4094 yeah, also noticed a lot of people have problems with insertion sort, maybe because of while loop (TBH it is my favourite of simple sorts). But selection sort is as simple in implementation as bubble and also more natural. IMHO selection have even simpler implementation than bubble.

@T33K3SS3LCH3N

3 жыл бұрын

@@w01dnick at the start of my studies, one of my first programming assignments was to write a sorting function in java for an int array, before we had received any teaching about sorting algorithms. I racked my brain a bit and ultimately "invented" my own Bubble Sort. That's why it's always my go-to example for a simple sorting algorithm. In hindsight I have no idea why, since Selection Sort *should* be more intuitive. But it's not like Bubble Sort is very complicated either.

@ebenolivier2762

3 жыл бұрын

Bubble sort is actually very good when the list is almost sorted. Like if you want to sort polygon vertices by z order in a 3D game.

This is the aussiest video I have ever seen... this week. Great video, especially for someone like me who doesn't have CS background! Thanks & greetings from Switzerland!

This was a really fun video! Very informative and entertaining! Going to watch your radix videos now

But if the list gets gigantic, you will run into another problem with some algorithms: Memory! Some require external storage as big as the list to to be sorted (radix sort, merge sort), some require at least some extra memory (e.g. recursive ones that require lots of stack space) and some entirely work inline, so as long as the list itself fits, you won't get a problem.

Man, I'm literally lmao on the third race 😂 with the pink one mocking the others algorithms 😂

Great idea to bring humor into this dry and often too serious world of programming :) I really enjoy your videos. I used shell sort for my commodore plus/4 3d-renderer and it was of course my favourite competitor in this wonderful race! (and its a really great algorithm)

Radix sort is definitely the best sorting algorithm... when you're sorting integers. One of my projects is a game engine, and it needs to depth-sort items before rendering. The depth is floating-point, so radix sort just doesn't quite cut it. Additionally, I need a stable sort so that objects happening to have the same depth don't flicker on top of each other. I am currently sticking to a simple stable merge sort, though the plan is to upgrade to a block merge sort when I get the chance. If I could figure out a way to reliably convert my floating point numbers into validly comparable integers, I would happily use radix sort, counting sort, or any of the similar ones. Thank you for the awesome video! You have earned my subscription.

@eddyecho

3 жыл бұрын

Use float_sort. Its faster than merge sort. www.boost.org/doc/libs/1_59_0/libs/sort/doc/html/sort/sort_hpp/float_sort.html

@Aristotle000001

3 жыл бұрын

Block merge sort is only really a space consumption upgrade though. Wouldn't an optimized bottom up merge sort be a better upgrade to fit your current constraints?

@Aristotle000001

3 жыл бұрын

@@eddyecho That actually seems pretty good, possibly the best solution.

@colemanengbrecht4448

3 жыл бұрын

It is possible to use radix sort to sort floating point numbers by converting them to a fixed point value represented as an integer. Also I'm pretty sure radix sort can be implemented stably by using a least significant digit algorithm.

@rayredondo8160

3 жыл бұрын

@@sebastianaaltonen1995 Thank you, and thank you all for your tips! After doing a bit more research, I am going to switch my sorting algorithm to an LSD radix sort implementation. After a bit of analysis, flipping the sign bit does not work, as greater magnitude negative numbers are still in reverse order. Then again, I could just disallow negative numbers, and anyone trying to use them is just invoking undefined behavior with regard to sorting. Anyways, thanks to *all* of you in the replies! I am not a sorting expert by any means, but you have helped me choose the right algorithm for the job today.

I love your videos! Please keep making more. Stuff like compilers, optimizations, SIMD, cpu cache, and algorithms are all so interesting! Maybe a Godbolt adventures #2?

@WhatsACreel

4 жыл бұрын

That's great! That vid got more views in 24 hours than any I've made before. Mr Godbolt himself commented! It was really fun :) I'd love to make more!

Brilliant way to illustrate the performance differences between different algorithms 👍

God I love your videos, your accent and personality. Fantastic stuff

@WhatsACreel

4 жыл бұрын

Haha, so nice of you to say! Cheers for watching mate :)

Good practical explanation. Thanks. Cheers

I think it's worth noting the difference between avg big O vs worst case big O. For example QuickSort is O(n log n) in the average case, but its worst case performance is O(n^2) while merge sort is O(n log n) in both the average and worst case.

@UnrealPerson

2 жыл бұрын

So quicksort is O(n^2) and Θ(n·log(n)).

What a brilliant channel. Love this guy.

First, wow... you actually made a sorting video nail-biting ... well done! Absolute genius! That 'slow-mo' was unexpected and hilarious! Me, I put all my money on Pink after the very first race! I knew that any working algorithm that couldn't sort 2 numbers - hadn't even got started yet. Even a blind random _(false)_ sorting algorithm would have got past the first checkpoint !!! So, Pink was clearly still "revving up" ... as soon as the brakes were released, I knew we'd see something spectacular ; ) ... I didn't count on him being such a show-off though XD

This is fascinating, great video!

Finally found a sport for me to enjoy!

Fun video but it's to easy for radix sort to win in those perfect conditions, if the data contained signed floats it would be very different.

@arglebargle17

3 жыл бұрын

Creel mentions that in another video. You'd have to modify the algorithm to essentially have buckets for negative and positive numbers, then exponents, then break down the mantissa the same way that you'd process unsigned integers. I may try this as an exercise. ASCII strings would generally be as simple as unsigned integers (I think). Sorting Unicode with relevant language pages might pose a bigger challenge. (I know enough Thai to know that I'd hate to try to collate it.)

@thorH.

2 жыл бұрын

@@arglebargle17 Im a beginner in Java and can confirm that it is really easy to do ASCII string sort as I just did that for practice. Its probably not the most optimized but it works quite well

@arglebargle17

2 жыл бұрын

@@thorH. Good on you if you're studying java and trying this. It's something I wish I knew this years ago when I ran into an awful situation at work where I could have done what you did and ended an interdepartmental war.

@thorH.

2 жыл бұрын

@@arglebargle17 How bad was it? That sounds pretty serious…

How I know I'm a nerd: excitement about sorting algorithms. Never change.

Really love how informative this video is about the different sorting algorithms

You had way too much fun making this :) Anyway, this proves that the standard library sort is good enough for everyday use.

The technical quality is awesome, but the part I enjoy the most is how (I think) he makes fun of the youtubers scene. And all the fake behaviour of those (unboxing and not only) puppets. Love it.

*This was my Favorite Video Dude :)*

The radix sort is the one used by the old card sorters. If a stack of punch cards has a number in a range of columns, say 73-80, you can order them on the card sorter. Put in reader, select a column, start. There are 10 bins, 0-9. Restack, repeat for other columns.

That was awesome Chris nice one mate.

@WhatsACreel

4 жыл бұрын

Thanks brus, cheers for watching :)

My Guesses For Who's Who (before they were revealed) Selection: Red ✅ Quick: Blue ❌ (actually Green) Insertion: Yellow ✅ Bubble: Purple ✅ Radix: Pink ✅ Shell: Brown ✅ STD: Green ❌ (actually Blue)

I think I found a sport I could get into 😂

Radix sort had enough time to use it's buckets to build a sand castle with all that dust buildup inside your computer while waiting for the others to finish

Truly funny 😂 How about a derby, with algorithms as horses, compilers as jockeys and memory usage as handicaps? Keep going, your content is great! 👍

This is the most excited I've been to watch sorting algorithms !!

This was a blast! Thank you for putting it together and sharing 👍😎🇦🇺

Back in the late '70s, I got stuck maintaining a home brew inventory system for a company that built array processors. (The company's product was not used to manage inventory.) The system was written in FORTRAN IV, and used bubble sorts to perform parts explosions. It ran over the course of the weekend, and had to be babysat. Realize that the super-mini that it ran on and was a 16-bit machine with 1 MB RAM. We bought a sort-merge package for over a year's salary and integrated it with the system. It still took a long time to run.

You made sorting fun. Crazy! BTW, we sort billions of elements all the time. So much data that it can't all fit in memory at once. And it's 2d or 3d coordinates that have to be sorted into quad trees or octtrees. These algorithm would make pink look as fast as lightning in that first round. Just one IO operation and the race is done by everyone else. What we do is multiple passes over the data. First pass is just counting how many points in each bucket. That way, we know which buckets can be kept in memory and which buckets need to be stored back on disk to be processed recursively later with even smaller buckets. Insanely slow for small datasets, but difficult to beat for terabytes of data. Oh, and the final sort is putting the data in Z order/curve with internal gridding. We want to eventually add Hilbert ordering as well.

@jacobstrength3945

Жыл бұрын

I have to ask, billions of elements of what?

ah yes sorting algorithm in recommended. quality content

You forget about bully sort, it works like this: Chose the first element. Remove the rest of the elements. Boom your array is sorted.

I'll be honest, I wrote this comment after the explanation. I like this video and the content. Excellent way of showing sorting algorithms in action

Nice video clip, keep it up, thank you for sharing it :)

This is one of my favorite videos about programming on KZread 👻

Pink: [ZA WARUDO]

Very Informative! I always thought quicksort is the fastest sort but i guess its Radix. You've earned a subscriber.

Gotta love the spellcheck underlining of radix

Super funny man! Excellent!

This channel is so fun.

What a great video!

This was so fun 😂 thanks for this

I don’t know what this is. I don’t know why this is in my recommended. I don’t even know what they’re sorting but I’m here for it.

If multiverse is real and multiverse is limitless there will be a universe that bogo sort always sorts arrays in only 1 round

Loved the video

i was right about radix! i had a feeling thats what it was when it was being better as the numbers increased (especially noticeable in the 2nd where it overtook because of the size increasing). edit: by right i mean right that it was pink.

I didn't think sorting algorithms would be the subject of lots of different things but I'm glad it is

i think pink is radix sort, and since stringifying numbers (i assume that’s what it does to actually get the digits?) is so slow, it lost in the first tiny race, but in later races goes way faster i think purple is bubble sort

@pawemarsza9515

3 жыл бұрын

Stringifying numbers would be absolutely terrible. Instead, in i-th iteration you remember either: 1) value of d^i, where d is your base (usually 10); if this value is named 'pow', then to get digit you do { (number / pow) % 10 } 2) bits to shift = i - 1; that means you perform radix sort in base 2, and get digit like this { (number >> (i-1)) & 0x00000001 } Overheads in early races arise from the fact, that complexity of radix sort is O(b * n), where b is number of digits in a number. When number of digits is bounded and small in comparison to n, let's say - 32 bits = 10 decimal digits vs 1000 000 elements in list, then we can say, that radix is O(n) But, for very small n, factor 'b' dominates, making radix perform horribly. Also, there is the need to allocate memory for counters, which is important when there is little elements to sort

Imagine being so damn cooked that you formally define a random permutation generator as a sorting algorithm.

I love me a natural mergesort 😍 I once had to sort a list of variable-sized items in-place using constant memory space (this was on a Z80 sorting a poorly designed "Variable Allocation Table"), and I found that I couldn't do better than O(N^2), but I was able to eek out a win with natural mergesort over a natural insertion sort after something like 95 elements. I ended up using 26 bytes or so, including stack space, ram to hold pointers, and a small buffer to copy bytes to whenever I rotated the bytes in a buffer. Natural mergesort is even simpler than normal mergesort, especially when you don't want it to be recursive (and thus use O(log(n)) stack space). The reason for why even a traditionally O(nlog(n)) algo took O(n^2) time was because of how expensive it was to move an element in that situation. It had to be in-place, and to swap an element, you had to move something like O(n) or O(log(n)) bytes (I can't remember) instead of O(1) (the elements were variable sized, but constrained to 8 to 15 bytes).

Hey radix ! can you just make sure those 2 boxes ? Radix : Yes sure ! i'll just jump quick at the workshop grab my tools for measuring boxes and i'll be doing it in a blink of an eye !

There is an even faster sort. It's not linear, it's scalar. It's spaghetti sort. If you want to sort spaghetti by length, you just place them all on the table with their ends and let them drop while keeping them upright and you're done.

I love this channel

Very good presentation

before the competitors are revealed: I think pink is the radix sort, since it was so slow at the begining, but got really fast in the larger lists. also, You should have included bogosort.

@WhatsACreel

3 жыл бұрын

Nailed it! Haha, I was thinking about bogo too! It would be funny to show :)

love the mullet dude!

Really enjoyed this! Do people ever design their own sorting algorithms?

It seems that taking advantage of data typing as a radix is very beneficial, and it's not just integers that you can take advantage of, there are also strings and a very simple way with floats (you don't consider the exponent as an exponential, you can define it as: sign (mantissa + uint (exponent) * 2 ^ (k + 1)) where k is the size of the mantissa in bits, the conversion to uint is to shift -128 to 127 to 0 to 255, you can turn this into an integer) .

Am i the only one that does not see pink there ? I had to color pick with chrome devtools and google the colorname #ffcc99, it said peach/orange. Pink should be more red-ish for my taste. Why is he calling it 'pink', and no one is complaining?

@Erlisch1337

3 жыл бұрын

You are correct. Its defenitly not pink. Its not even remotely close to pink.

@T33K3SS3LCH3N

3 жыл бұрын

I'd call it beige or skin tone (although that's obviously a very local term in our globalised world). Pink is kinda interesting in that many people have different ideas of what it really means. Even in more professional definitions it can cover a very wide range from a rich magenta to a pale grey-ish colour. This one is still outside the usual definition though.

@DaemonWorx

3 жыл бұрын

Agreed

@asandax6

3 жыл бұрын

I have no idea why he's calling it pink just as why people call foxes Red while they are clearly orange.

@riccardoorlando2262

3 жыл бұрын

I would definitely have called that color "pink". Cultural differences ahoy.

great video!!.

I came here again to hear him say "Elements"

it trips me up whenever you say pink and i don’t see a punk one on the screen lol. i guess my mind has engrained that colour as beige.

I like Ford-Johnson sorting, followed by quicksort with insertion sort at the leaves. All these other algorithms are less efficient, except that radix sort is fastest when the keys permit.

Question: which increment sequence did you use for Shellsort? There's a number of good ones, but they do have different characteristics, and it's important to avoid the bad ones.

Pink Ran so fast it got bored and decided to go again but got bored again and decided to again it was literally running circles around everyone. I love races and Algorithms

That was fun!

I remember in the '70s when SyncSort advertised the fastest sort compared to the IBM Sort. There was a lot riding on the fastest sort because almost every job stream had at least one sort and often multiple sorts. A faster sort could shave minutes off of a job saving the company money each day!

I don't remember much from my data structures classes but I did remember O notation, bubble sort is slow at big data sets, and radix is weird but insanely fast at big data sets.

It would have been cool to see them race from 2 elements to 200k. It would be interesting to see if pink could have made a come back after its slow sort once it picked up speed at larger sizes.

I believe in Bogo sort, one of the best sorting algorithms in the world if you are lucky

8:05 "Because I want to avoid too many digits on the screen"

After that first race the first thing that came to my mind was that pink was bubble sort... Boy was I wrong

@HiAdrian

4 жыл бұрын

Same! 🙃

@WhatsACreel

4 жыл бұрын

I was surprised by some of the results while timing them too! Certainly didn't expect Radix to be soooo slow! Cheers for watching :)

@taemyr

3 жыл бұрын

A well implemented bubble sort will perform reasonably well on small size lists. Pink was way to slow to be bubble sort, I was looking at it and wondering if they had included bogosort. But that would not work either, because bogosort would be extremely unlikely to e that slow for a list of two elements. Then I realized that complexity of radix sort scales linearly with the size of the key.

This is one of the nerdiest thing I've ever watched...And I enjoyed so much!!

Well, on paper O(n) sounds good. But its easy to forget that additionally to scaling with the size of the list, radix sort also scales with the amount of possible values in the list, the others don't. So radix sort is pretty useless for cases where you have a lot of possible values, but not many elements. It is only good in a case where you have a lot of elements, with not many possibilities.

@WhatsACreel

3 жыл бұрын

That's true, Radix Sort does scale if your keys are arbitrarily differing lengths. But we often use it to sort lists where the keys are of a fixed length. 32 or 64 bit integers, for example. Then the number of iterations Radix Sort is also fixed. It's a very fast sort mate! Certainly not the best choice all the time, but a very decent all-rounder! Cheers for watching, have a good one :)

@jort93z

3 жыл бұрын

@@WhatsACreel Well, but radix sort with 64 bit integers will take twice as long as radix sort with 32 bit integers. Something like quicksort won't take considerably longer. The complexity of a radix sort is something like O(n*w), where w is the key length. All the other sorting algorithms don't scale with key length. So I think you can't really call it linear, it just scales with different factors.

@WhatsACreel

3 жыл бұрын

@@jort93z Yes, that's right. I'm not saying you're wrong. The time is O(n*w), just as you said, but if the keys are a fixed length, then "w" is a constant, and the time becomes O(n). If you're sorting BigInt's or strings, or any data of arbitrary length, then it's probs gonna be O(n*w). But if you're sorting ints, 64 bit ints, floats, or doubles, then it'll be closer to O(n). I don't mind which you're sorting, and I don't mind which Big O you like best, all I want you to do is have a great day :)

@catprog

3 жыл бұрын

@@WhatsACreel Strings means you have 26 buckets labeled A-Z. Instead of 10 labeled 0-9. Or if you wanted to get really complicated 0000-1111 in binary.

Cool video)