ฝัง
- เผยแพร่เมื่อ 22 พ.ค. 2024
- In this video, we race 7 sorting algorithms against each with lists of varying sizes. This is meant to demonstrate the different strengths of various algorithms, and show which you would be best using when given data sizes to sort.
I have included the Patreons that made this video possible below. Thank you for your support mates :)
Sources for original algorithms:
Quicksort: en.wikipedia.org/wiki/Quicksort
Radix sort: www.geeksforgeeks.org/radix-s...
(Change the base to 256 if you use this code!)
Bubble Sort: en.wikipedia.org/wiki/Bubble_...
Selection Sort: en.wikipedia.org/wiki/Selecti...
Insertion Sort: en.wikipedia.org/wiki/Inserti...
Shell Sort: en.wikipedia.org/wiki/Shellsort
Support What's a Creel? on Patreon:
/ whatsacreel
FaceBook:
/ whatsacreel
Music Channel:
/ @creelsmusic5814
Another channel with random things:
/ @ftlol6091
Patreons:
Alexander Dahlin
Alve Larsson
Augusto Righetto
Awon Ali
Blaz
Carsten Hansen
Cato Larsen
Chris Lidyard
Christer Borgqvist
Curtis Seizert
Darby Burbidge
dominic pace
Dominik Wyss
Floris Bob van Elzelingen
Geert Depuydt
Gurpreet Singh
James Mearns
Jeffrey Knuckle
Josef Aguilar
Joshua Smyth
Luke Duguid
Martin Champagne
Martin Cohen
Matheus Salvia
Matthew Livernoche
Micah Rust
Michael Pearce
Patreonic
Pavel Bibergal
Rahul Nair
Renwick Preston
Robert Jacobson
Roman Kozak
Ross Young
Steffen André Langnes
Taylor
Thomas
Todd Cullum
Tom Marazzo
Wathinti Abafazi
William Allen
Yichao Shen
Zhixun He
Software used to make this vid:
Visual Studio 2019 Community:
www.visualstudio.com/downloads/
Synfig:
www.synfig.org/
Gimp:
www.gimp.org/
Audacity:
www.audacityteam.org/
OBS:
obsproject.com/
Davinci Resolve 16:
www.blackmagicdesign.com/prod...
Some say BogoSort is still drinking beer halfway the first race.
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.
@@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
nah, it got lucky and sorted every list first try...
@@bastian_5975 This is why best case Bogosort has a big O notation of O(1)
@@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
the best analogy of radix sort i have ever read
That was actually very helpful!
Though it works pretty well when you trip and drop your FORTRAN source deck.
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
speak for yourself buddy i am ecstatic to see any sorting algorithm
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
Hahaha, this is awesome!
The only reason is that it had enoght memory.
@@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
Haha, this is great!
@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
Sleep sort is better than o(n), it's o(1): www.geeksforgeeks.org/sleep-sort-king-laziness-sorting-sleeping/
@@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.
@@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.
I knew purple was bubble sort because it was the only one moving at a constant speed the whole time throughout every race.
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.
After the first round, I assumed pink was bogosort under a different name.
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.
@@hardlyb that is what I call dedication.
@@TheJas-vr2vr I was thinking it was too. Then when I saw the final race... I was certain.
bogo just yeets and sort in oneshot
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
Looking at you, quicksort!
@@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!"
@@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.
@@nolifeorname5731 🤣
@@Kromaatikse .
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
Now THIS is Computer Science
Cheers mate :) Thanks for watching!
now THIS is podracing
Funny how everyone always includes bubble sort in these things, even though the only advantage it has is sheer simplicity.
Bubble Sort is there as the "banana for scale".
It doesn't even have much of a simplicity advantage. Insertion sort requires roughly the same amount of code, while actually being useful.
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.
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
@@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
Me: Ok 5 hours sleep should be just enough to see me through work tomorrow
My brain: But which algorithm is actually fastest overall?!
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 :)
11:30 I'm dying here 😂🤣🤣🤣Pink taking the piss out of everyone
greatest anime plot twist lol
I would appreciate comparison of random-sorted data, partially sorted data and reverse sorted data..
Unfairly partitioned data and data producing hash collisions would be great fodder for these benchmarks.
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.
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.
Very nice illustration why hybrid sorting algorithms are so popular where small sublists are sorted with something simpler than the large list.
the disappointment of placing my bets on pink in the first race. i have been shattered
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
I would give anything for a teacher like you in my school. The idea was great and interesting. Thank you :D
I'm so happy people find my humble offerings valuable! Cheers for watching mate :)
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.
So mergesort
@@mitlanderson std sort is quicksort+ heapsort, and it literally just starts using quicksort, and if quicksort takes too long it switches to heapsort.
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.
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
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?
@@eddyecho That actually seems pretty good, possibly the best solution.
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.
@@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 was laughing so hard watching the poor bubble sort shambling through the 2nd race - it was pretty obvious who that one was ;)
This video got an "instant subscribe" for me. By far the most interesting algorithm comparison to watch! Amazing job!
Man, I'm literally lmao on the third race 😂 with the pink one mocking the others algorithms 😂
pink is basically sonic. Slows down to give people a chance, but when it comes to a true challenge goes all out
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)
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.
Really love how informative this video is about the different sorting algorithms
This was a really fun video! Very informative and entertaining! Going to watch your radix videos now
Brilliant way to illustrate the performance differences between different algorithms 👍
What a brilliant channel. Love this guy.
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?
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!
Good practical explanation. Thanks. Cheers
Go bubble sort! Time to prove the haters wrong!
Never understood why people think bubble sort is simple. To me selection sort is much more natural and easier to implement.
Btw, insertion sort is also much more natural than bubble to me. People usually sort cards that way.
@@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.
@@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.
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.
You had way too much fun making this :)
Anyway, this proves that the standard library sort is good enough for everyday use.
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.
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!
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.
God I love your videos, your accent and personality. Fantastic stuff
Haha, so nice of you to say! Cheers for watching mate :)
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.
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.
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.)
@@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
@@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.
@@arglebargle17 How bad was it? That sounds pretty serious…
This is fascinating, great video!
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)
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.
I have to ask, billions of elements of what?
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.
So quicksort is O(n^2) and Θ(n·log(n)).
This was a blast! Thank you for putting it together and sharing 👍😎🇦🇺
*This was my Favorite Video Dude :)*
Truly funny 😂 How about a derby, with algorithms as horses, compilers as jockeys and memory usage as handicaps? Keep going, your content is great! 👍
How I know I'm a nerd: excitement about sorting algorithms. Never change.
Very Informative! I always thought quicksort is the fastest sort but i guess its Radix. You've earned a subscriber.
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
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
This is one of my favorite videos about programming on TH-cam 👻
Finally found a sport for me to enjoy!
Pink: [ZA WARUDO]
I think I found a sport I could get into 😂
Nice video clip, keep it up, thank you for sharing it :)
That was awesome Chris nice one mate.
Thanks brus, cheers for watching :)
This is the most excited I've been to watch 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) .
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.
Gotta love the spellcheck underlining of radix
Very good presentation
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).
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.
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.
Super funny man! Excellent!
Really enjoyed this! Do people ever design their own sorting algorithms?
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.
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 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
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
This channel is so fun.
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.
What a great video!
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 !
This was so fun 😂 thanks for this
love the mullet dude!
If multiverse is real and multiverse is limitless there will be a universe that bogo sort always sorts arrays in only 1 round
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
Imagine being so damn cooked that you formally define a random permutation generator as a sorting algorithm.
The setup time can hurt. Back in the day, had a system that needed to sort an array in memory in 640K. The runtime sort took too long, it was fairly large. Wrote a quicksort. Randomly swapped a few before start just in case to avoid pathological outcome. Never needed to change it, worked well.
Loved the video
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?
You are correct. Its defenitly not pink. Its not even remotely close to pink.
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.
Agreed
I have no idea why he's calling it pink just as why people call foxes Red while they are clearly orange.
I would definitely have called that color "pink". Cultural differences ahoy.
I came here again to hear him say
"Elements"
How often do you need to sort? Add, Remove, Change/Rename, I usually do with binary trees, that I put into more bushy when it is less busy.
8:05 "Because I want to avoid too many digits on the screen"
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.
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 :)
@@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.
@@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 :)
@@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.
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!
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.
Nailed it! Haha, I was thinking about bogo too! It would be funny to show :)
This is one of the nerdiest thing I've ever watched...And I enjoyed so much!!
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.
great video!!.
We need a longer marathon !
I'm not familiar with STD, Shell, or Radix sorts. By the end of race 2, I was pretty sure that yellow, red, and purple were insertion, selection, and bubble sorts, in some order. I knew this because I knew these sorts are "beginner" sorts taught to introduce the overall concept of sorting in a simple way, but that they do not scale particularly well. Specifically, I knew they scaled by O(n^2). Seeing the results of race 3 confirmed this because their 200k times were all about quadruple their 100k times, and that's exactly how O(n^2) works.
I also expected quicksort to do particularly well because it scales by O(n*log(n)). In fact, I'm pretty sure that O(n*log(n)) is the fastest you can possibly get a sorting algorithm to go in the average case for lists of all types. I don't know what black magic Radix is up to that lets it scale by O(n), but I suspect that it only works under certain conditions.
Radix's sort secret is that is that it's a non-comparison sort. Here's a link to creel's video giving a full explanation: th-cam.com/video/_KhZ7F-jOlI/w-d-xo.html
Inserting all the items into a std::set and std::multiset should have been added as sorting algorithms - basically using a red-black tree to keep the list in order from the start. An AVL tree would be interesting to compare with red-black.
The initial order of the data can have a huge impact on the performance as well. There should be already-sorted, reverse-sorted, bitrev-sorted (butterfly order), shuffled blocks of increasing values, and random order with more than one seed. Algorithms can have pathological or optimal performance in one of those scenarios. Pathological input is likely to be well handled by good implementations.
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.