Radix sort is exactly how punched card sorters worked in ancient times. The machine had a bin for each punch position. (There were 12 punch positions in each column.) The card deck was run through the sorter once for each digit position, and the bucket contents picked up in order, the deck restacked, and run through the sorter for the next punch position until the entire sort key had been covered. Sorting a couple of thousand cards could be done quite quickly.
Such equipment went by the name Unit Record Machines. This category of hardware included sorters, simple calculation tools (adders, multipliers, subtracts and dividers, for instance) and printers.
I worked in a clearing bank in London back in the '60s and we used the same technique to sort cheques by account number, by magnetising the digits on the cheques and reading them. Eight passes for the account number which also sorted in branch order. The cheques had already had anything other than those that belonged to the bank removed and sent to the other bank. London cheque clearing in action.
A few years ago I was working on a project to create a bounding volume hierarchy for collision detection, and as part of organizing the objects (along a space-filling curve for efficiency's sake) I followed some technical papers to create a GPU-based, parallel binary radix sort. It was fast, and the particles that were being collided never had to leave GPU memory. But it was a right beast.
Decrementing the prefix sum serves two purposes: 1) converting to a zero-based index, and 2) avoiding collisions in the output array. The latter is accomplished by updating the value stored in the prefix sum array. This is a crucial point that should be stated explicitly.
I've seen many youtube videos and papers on this matter and I must say that I never have seen sorting algorithms explained so simply and with such passion! I really liked how you explained the logic behind comparison based sorts on part 1, it's really useful to understand sorting networks and their limitations. You are an excellent teacher and hands down one of the best youtube channels on this matter! Btw, just a note: to implement radix sort for signed integers you just need to do the prefix sum in the last digit that includes the signed bit in a different order, going from the middle of the array to end and then from the start to the middle again so that the digits starting with 1 (the negatives) appear first. For floats the idea is similar, but instead, you also have to do the first partition of the prefix sum in reverse order (going from the end of the array to the middle, and then from the start to the middle again) and then you adjust the scattering part so it decrements the pointers corresponding to numbers from the first partition. There are also bit flipping solutions, so you don't need an extra radix pass.
@@Wyld1one it won't work, we start from the once's place, if you want to do -9 to 9 i'll add some overhead such as add +9 to your counts etc etc, and would also have to check the -ve every digit cycle
This is literally the only channel on youtube about programming that i watch solely because the videos are made so engaging and fun, and not because i have to prepare for test. Best channel
I’m just a random 20yo student and I discovered this channel out of YT’s algorithm Loved it after only one vid, subbed and have been binge watching this on this rainy sunday afternoon, sipping coffee. My life is pointless but at least I’m learning cool stuff
Hey mate, your life isn't pointless! I found this channel last night, and it's been great. I "graduated early" with a 2-year degree in electrical engineering a long while ago, never used it outside of school unfortunately.. and today I'm employed as a full stack dev with 7+ years of professional experience in that position. Life can be crazy, and I don't know much about it (yet!), but I know for sure, your life isn't pointless :) This is an old post, but hit me up if you wanna chat, or have any questions about anything. Much love.
if you "really" learn this, by which I mean you understand to the degree that you can explain it to others well by yourself, you are already on track to a great career as a good software engineer. In time, you'll build yourself a good career at a software company like Microsoft or Google. Regardless of whether you like the companies, you'll at least set yourself up for a good salary which'll enable you to do what you like. Keep it up!! - source : I'm a senior software engineer at Google myself.
Your energy and accent remind me of Steve Irwin! "Crikey! It's a radix sort! Now, we'll just sneak up behind heeeem and grab heeeem behind the head....... " Cheers from New Zealand!
Ok, this just randomly turns up in my YT feed for no apparent reason, even though it's old and I haven't watched a coding video in literally years. But thanks, algorithm, for knowing me better than I know myself, because I loved it!
Seriously Mate, your this series ... I am a CS Student of 3rd Semester. We haven't started Data Structures and Algorithms yet, but will soon be (from 15th of Sept). And I am feeling so lucky, that you are making such a Great Series of videos based on Algorithms! This Counting and Radix Sort got me curious to understand all types of Sorting and other Algorithms. All Thanks to you mate :)
Right after I graduated from university, I did some travelling and ended up doing odd jobs at a travel tour company. It happened to be the end of the fiscal year and given that this was more decades ago than I'd like to admit, they had a mountain of physical files that needed sorting. Usually they spent 2 whole weeks to sort the files. They asked me to sort it. I can't remember exactly how I set it up, but I took over several desks and made my "buckets". Bucket sort works *really* well with physical files because concatenating them back into the original pile is simple :-). I got it all done in an afternoon and after that they thought I was a genius :-D
The complexity of the Radix Algorithm is dependent on the size of the largest number. So if you had just one max value 64bit integer, you would be running the counting algorithm 19 times.
Not really. If you do MSB radix sort it is perfectly possible to skip empty buckets and buckets of size one. As usual, real performance depends on implementation and data distribution.
Nothing stopping you from using 100, 1000 or 10,000 counters. Gets you down to ten, seven or five passes. 22 upvotes for you, but not a single bright bulb in the crowd for two years - yikes!
Your counters have to be < the size of the list. That is the problem with Radix sort, trying to find a balance between memory allocation and speed. Obv it also isn’t good for small lists.
Radix sort is O(d * n), where d is the length of the elements. For sorting elements whose length is shorter than log(n) radix sort absolutely blazes through the list. If sorting a list whose elements lengths are longer than log(n) radix sort actually performs worse than its contemporaries. Given that a randomly generated list of unique packed keys has a longest length of log(n) (you eventually run out of unique elements at any given length and have to add another digit), the d * n starts looking suspiciously similar to nlogn. However if you have a very long list of short, non-unique keys (if you wanted to sort a list of dice rolls or something I guess) this is absolutely the best way to do it!
If you have to sort a list of dice rolls, Just count them in an array of 6 bins. This will most likely be faster than radix. If for some reason you want a long list instead of a compact array with the same information, you can always generate it from the bin array in O(n) time
Nice video, but I have to complain about the supposition that radix sort is somehow O(n). Its extremely important to leave in the O(nd) where d is the number of digits. O(n) invites an extremely dangerous line of thinking where somehow people may come to the conclusion that radix sort somehow asymptotically beats nlog(n). It does in an extremely limited sense but its hardly the full story. Unless you have an exponentially increasing fraction of duplicates, then d must be of the same order as log(n). You can't represent 10,000 distinct numbers without at least 5 digits or ~log2(10)*5 = 15 bits. Suppose you are infact beating those bounds and d < log(n). Then at most (base^d/n) fraction of your array can be unique values by the pigeonhole principle. Concretely if you are beating it by 2 decimal digits or like 6.6 bits then at most 1% of your array is unique an the other 99% must be duplicates. Plus it makes it seem like log(n) is much faster growing then it is. In practice log(n) is strictly less then 64 on most machines. Its really not fair to make a "fixed word length" argument for radix sort and other comparision sorts because in reality you could never sort more then 2^64 elements on a machine with 64 bits of address space anyway.
Hello, I've got to agree and disagree. I hope that Mr Creel will talk more about the complexity in later videos, but I'd like to point out that the time complexity of Radix is actually *O(log[base b](k) * [n + b])* , or if you prefer *O(log(k)/log(b)*[n + b])* , where *b* is the number of _bins_ in the counting array (10, in our case), and *k = 1 + max_element - min_element* . Note that *b=10* was used in the video for _simplicity_ but its value should be dependent on the array input. If we set *b=n* , then *O(log[base b](k)*[n + b])* becomes *O(n*log[base n](k))* . We usually abbreviate *log[base n](k)* to *d* , but as you can see, how we count the number of digits changes as the input size grows. Informally: As the input size grows, Radix becomes increasingly insensitive to *k* even if *k* grows polynomially with respect to the size of the array. Radix is a bad choice when *k* is high _and_ *n* is small; specifically when *k > n^log(n)*
I’d say you are both right! The proper time complexity is O(nd). Keys are often fixed in size. Not always, of course, but often. We tend to use 256 as the radix, resulting in 4 iterations with 32 bit unsigned ints. So, it’s true that radix sort’s time complexity is more subtle than O(n), but it’s also true that in practice it tends to perform at about O(n). I’d add that the time complexity for many things is subtle. Addition, for instance, requires O(1), so long as you have a machine that has an Add instruction with an arbitrary number of bits. Otherwise, it’s O(n) with n being the number of bits. Measuring the performance of algorithms is deep and complicated. Thank you for the info, and thank you for watching :)
@@elliott8175 that is correct, i found your comment right after explaining the exact same thing in mine. In O((n+b) log k / log b) each value can become a bottleneck. Sure, most of the time N will bottleneck, but so can higher than optimal base and higher than optional range. Especially when sorting binaries, fixed point floats, strings, etc.
The way he explains radix sort... yes his version is not linear. In real radix sorts you always go most significant bit first. This means that after the first iteration you have a mostly sorted array and boundaries for all unsorted portions so you can recurse and sort the sub arrays or switch to quick sort in the subarrays. Aka burstsort.
I love the way you present yourself and talk about these subjects. I've learned great things on this channel that I didn't even ask to learn, but just watched for entertainment xD
I love watching those animated sort algorithm demonstrations, and Radix sort was always one that looked neat... but your explanation is fantastic! I finally understand it, and goddamn, is it freaking clever! :D
Awesome stuff. Around 15:30, when talking about how to apply the prefix sum, I was thinking of the interpretation that the prefix sum is the running total of numbers with lower digits. So in the first iteration for 721, which end with 1, you are looking up how many items end with 1 or lower. And for 779 you are looking up how many numbers end with 9 or lower, etc. For each number, that tells you how many elements that need to be placed before that number, which also tells you the index of where to place it.
one thing that you can take advantage of in some languages is using something other than strictly an array for counting, so you can just leave holes where there are no items with that value, rather than having a bunch of memory full of 0's. unfortunately it's usually slower because these data structures have more overhead than arrays do.
This is an great idea! I think it would be especially useful for Radix Sorting smaller arrays. If we didn't need to Zero the entire digit array each round, might save some time! Cheers for watching mate, and cheers for the info :)
I'm not so sure. I don't know of any random-access data type that you can iterate over (for providing the solution), without having these "holes". We could provide a second mapping array, but this requires a sort to know how to get the right mapping (circular dependencies). Whether it's possible to sort in linear time is still an open question. Radix comes really close, but isn't actually linear. If we were able to use an array "without the holes" then I think we'd have solved this famous problem and be rather famous (among CS geeks) - so my guess is the appropriate data structure doesn't (yet) exist.
@@elliott8175 I was thinking you might be able to do that with a hash map, but it would require a special hashing algorithm that not only produces semi uniqueness, but ALSO internally stores larger keys after smaller keys, which is the bit we are missing. Maybe a fancy hash algorithm that tweaks itself on the fly in response to the data and performs some acceptable amount of rebalancing yadda yadda. Obviously I dont know the answer. It could also end up that just computing the hash is slow enough that it kills the idea.
Indeed it does! A viewer from the last video mentioned he did a talk on implementing Radix Sort for strings at JuliaCon last year! His talk can be viewed at: th-cam.com/video/C65vYWeN7-k/w-d-xo.html
It's actually potentially much better with strings because comparisons can take a lot of time with strings, but accessing a single character is fast. The bad news is you probably can't make this work with unicode easily. A string comparison in unicode is already an unsolved problem so you may not care about that.
@@vylbird8014 The problem in Unicode is two string can look identical when you render them but don't have the same representation. Even normalization doesn't deal with every subtle thing. So while it will be consistent, it may give you results you don't want.
@@meneldal You just need to transform your Unicode strings into byte strings such that the desired ordering is preserved. For example, the C standard library includes strxfrm() and wcsxfrm() for exactly that purpose.
I discovered your channel like yesterday, and as a game programmer in training I love your videos, you always explain things perfectly. Keep up the good work
Very informative and easy to understand! I think it was well-paced for beginners, as well as for people to whom the particular topic is novel, but the concepts familiar.
Beautiful content, Thanks for the amazing explanation and visuals, it's clear that you love what you are teaching and that makes the videos more than perfect
10:41: "We've got the input list just here... same elements as before, I think..." "Well, you wrote it, mate!" =)) What's a Creel playing both the teacher and the student for our amusement. Question: for integers, if you know you're big-endian, isn't it easier to simply build the counter array to have power-of-two buckets (like 8 or 16) ? And then, instead of doing mod 10, simply read the relevant 3-4 bits, put in the relevant bucket, and so on. You also have to make sure to have the sign bit in it's own step. Also, would it help to construct all the count arrays at once, so you only traverse forward the array once ? It uses a bit more memory, but arrays of 16 integers... doesn't sound that bad. Worst case for normal integers would be to compare 64 bit signed integers, and that would amount to 64/4 + 1 = 17 count arrays (the extra one is for the sign count array). Cheers!
@@WhatsACreel Performing AND on LS 4 bits, then AND on MS 4 bits with SHR to bucket count and sorting process used on byte size numbers ! If needed, Scale up by groups of 4 !
Great video series. Radix getting the attention it deserves! I would point out though that I don't think that Radix is a compromise between speed and memory (when compared to Counting Sort). If k is (1 + max_element - min_element), then counting sort has O(k) space complexity **and** O(n+k) time complexity (auxiliary array requires linear traversal: first to initialise to 0, then to load the solutions). This is just as much of a time problem as a memory problem, so Radix helps to handle both of these.
Back in the day, I encountered a radix-2 sort that was coded for a PDP-8 with two LincTapes (or DECtapes, which were just LINCtapes rebranded). Random access tapes - there was a timing track so that you could read and write anywhere, not just at the end of the tape. The buckets were accumulated in odd- and even-numbered sectors on the output tape. There was a weird trick where alternating passes through the tapes read the tapes backward. Nothing like sorting a megabyte of data on a machine with 16 kilobytes of core memory! When I jot a job as a mainframer, I encountered five-tape read-backward polyphase merge. Insane!
well strictly speaking, it's not O(n). it's O((n+b) *log k/log b), where k is the largest number you're sorting and b is the base of its integer representation. because of this, it might be better to use base-2 representation to minimize b term or to use base-10 or even something like base-256 representation to maximize the divisor. so assuming that k and b are constants is not always precise, because you might actually want to change them to make the algorithm run at maximum speed.
Right you are! The third video shows the code and performance of a base 256 Radix Sort! I agree that the performance is logarithmic when sorting data or arbitrary lengths. It's only O(n) when the length of the keys is fixed. Cheers for watching anywho, have a good one :)
I would call it O(N log R) where R is the number of bits. No need to change base as that is just a constant that gets simplified away by the definition of Big-O But I agree that it's not fully honest to call it O(N).
Okay, this is awesome! I've been trying to figure out a smart way to implement Radix Sort for a while, and you just gave me a way! Thank you for the awesome videos, keep doing awesome!
No worries mate! Links to the original sources as well as my own version of the code will be provided in the final video. I hope to upload it later today. Thank you for watching :)
Right now I´m studying "Computer Science" and i am learning for something we call "Algorithms and Datastructures". These 3 videos were actually shorter and way better than the ones from university. I can´t find something for big O notation in general from you. Do you have Videos for that topic? Anyway i reallly love your vids! Keep on Doing these! And sorry for bad english.
Wait ... For Big 'O Notation, you can check the channel of : *CS Dojo* . When "What's Creel" said about Big 'O notations, I instantly jumped to his tutorial :), and got the concept. Then came here to understand this. By the way, Great explanation.
Watched the first video and was going to propose what you called "counting sort"; my idea was to determine min/max and only use counts that fall in that range.
I;m old enough to remember how the old IBM punched card machines were used for sorting. It was a radix sort, and the "buckets" were actual buckets or slots that a card would fall into, if, say, column 35 were punched with a 3. You'd then gather the 10 buckets up in order, and run the deck through again, soring on column 36 (or whatever).
Amazing mini-series! Thanks a ton for taking the time and effort to make the beautiful presentations. Much appreciated. And, on a different note, is that a cat holding a cricket bat? I'm talking about the picture behind you.
thanks mate i appreciate your approach to these videos. you are very human and i can really get a feel for the worth / importance of each thing you mention. thanks man
Please do a video on how Radix Sort performs with differently based numbering systems, like binary or hex. I'd assume larger based numbers rely more on storage and read/write speeds, and smaller based numbers like binary rely on processing speed instead. Thank you! EDIT: Sorry, didn't see the other video you posted. Watching it now!
awesome stuff! also you're really good at explaining all this, it's all so simple to understand compared to some other explanations out there, awesome work!
Brilliant, and such an awesome explanation. Only improvement would be to mention to subtract 1 from the prefix sum for *each* time you move an input to the ouput, not only once (all the talk of moving from 0 to 1 base counting confused that part for me). Slow-mo'ing the part where you go through the rest of the items real fast helped me see what you where doing to make it work. Thanks for sharing!
An alternative approach would be to shift all the counts to the right and set the count of 0 to zero. In this approach, you would iterate from left to right and increment the counts instead of decrementing them. You would not have to convert between base 0 and 1 in this approach.
I agree, very clearly explained. After watching this video, (plus the previous videos reference to a mask and right shift) I wrote a working 16 bucket radix sort in 10 minutes.
Thank you man. I discovered radix sort in this crazy guy videos that make animated sorting algorithms with sound, and it's a lot of fun to watch, but not I finally understand how it works. It's a kind of magic ;).
The "bucket" version of radix sort is exactly how you sorted cards in an old mechanical punch card sorter. It took as many passes as there are digits. So you had to pull the cards out of the output stacks and stack them up in the input. Programs stored on punch cards would often be numbered in steps of ten in the last 8 columns. This way to insert a line after line #1000 of a 100 card stack, you would number the new card as 1001. If you go with 16 counters (AKA 4 bit digits), the counters can be on the stack. On most machines, allocating 16 words of stack takes no extra time at the routine entry. Sorting strings of text or other large things can often be more efficient if you make arrays of pointers.
That's right! I forgot about that... anyone who ever dropped their program card deck (or who's wise cracking buddy gave it a toss) but was wise enough to put line numbers on the cards knows all about this.
@@rhymereason3449 The new discussion of it is sort of an "everything old is new again" thing. The cards were invented for the US census before computers were machines. The mechanical "tabulator" let the government work out how many plumbers owned cats without any electronics needed.
I didn't see you mention that when building the output array, you increment the index in the count array, to handle where the same digit is repeated. The prefix sum has already taken this into account.
Also had to replay a couple of times to understand this, but I believe it's DEcrement rather then INcrement, right? He decrements the prefix sum and the next time the same digit occurs the prefix sum is already decremented and gets decremented once again
@@SergeyNeskhodovskiy yes, and that's also why you move from the end of the array to the start. You move the higher numbers into position first, then decrement so that the next position in the prefix sum is next highest number
This is actually pretty irritating. He decrements the index of each value once it is accessed so that repeat numbers don't land up in the same spot. It's a major omission that will cause people who don't know what a radix sort is.
@@disekjoumoer he certain does mention that you decrement the values in the prefix sum. Do you mean he didn't take the additional step of explaining the second purpose of it?
@@disekjoumoer He does mention that though. I agree he should have made it a bit more explicit, but he *does* say you need to decrement it after accessing it.
I was implementing radix sort by my own and I was surprised when my algorithm managed a total of 10GB RAM (not at same time, of course, but the sum of all allocating and deallocating operations). To improve it first I tried to do a better approach for bucket vector: instead of allocating 1 extra position by push operation, I would double the allocated size and use a second length prop to measure the vector. After that, I could reduce the 10GB total handled RAM to 400MB. Watching the video, an idea instantly clicked in my mind when I saw the digit counting array: "I CAN PREDICT THE BUCKET SIZE BY ITERATION!!!!" then I stopped video and did it. Reduced from 400MB to 100MB total handled memory.
You can iterate the input array from the left if you use an exclusive prefix scan instead (add up all the elements up before but not including the slot)
So the overall lesson is: know your data. The digits of a base-10 number, as well as the bytes or nibbles or even bits of a base-2 number, contain much more information than just x < y. Because every digit (or byte, bit...) is already classifying the number according to some power of 10 (or 2). If you can exploit that, you don't need to perform N log N comparisons. In fact, I think the same technique can be applied to fixed- or bounded-width strings, dates and times, tuples... By the way, I didn't know N log N came from log N!, that's very interesting. Here's a simple proof I found online (not taking the credit) Proof that O(log n!) ⊆ O(n log n): *log n!* = log(1 · 2 ⋯ n) = log 1 + log 2 + ⋯ + log n ** log n/2 + ⋯ + log n *>* ⌊n/2⌋ · log ⌊n/2⌋ ∊ O(n log n) Therefore O(log n!) = O(n log n) ∎
G'day, matey! Thank you again, here's one for the algorithm ! Btw, loved the little joke between you and the presentation with the same different set of numbers, haha.
When building the prefix sum , if you begin one index offset, (sum in index 0 is 0, second index 1 is sum of 0’s and so on). Then if you iterate from left to right when building the output array, you would place the element in the index specified by the prefix sum and then increment count.
I would like to see a pinned comment about repeating digits when decreasing the prefix index... I did not realize that you do not reset the prefix index and "accumulate" the -1 so that identical digits don't get the same spot... I had to go through many comments before I found the answer to that Interrogation... The rest of the video is really informative, thank you!
Great video! I'd never looked at how radix sort works under the hood. I paused the video at 16:36 and I started prototyping a radix sort algorithm... And it works! It is even faster than std::sort! Two points though: - is there a clever way to know when the array is sorted to avoid unnecessary iterations? - can this algorithm work with a user defined comparison function?
This is the first time I've heard of counting and radix sorts. I've always assumed that quicksort and merge sort were the fastest sorts. But once you began describing counting sorts I quickly got the idea of how it worked.
Hehe, there's a lot of sorting algorithms that are way faster or have better worst cases than the usually default implementations, but they usually consider the data to be sorted and may require more memory. Quicksort doesn't require any extra memory. Another example of better worst case ("faster big O notation") that works with pretty much any comparable data, that has better worst case, only takes up about twice the memory, easily implemented and understood, is tree sort. Just insert items into a self balancing tree (log(n)), then traverse the tree in order AKA O(n*log(n)). That's a very stable sort, best, average and worst case is all the same.
This was very good. I wish that more had been put into explaining the prefix sum - some of the mechanics were quite obvious and didn't need as much explanation as that did. I know it's a lot of work to do these things so thank you and at least it has given me a question to find an answer for.
Thank you for the video, I really enjoyed watching it. I would want, however, to put an emphasis on the witchcraft that let you rebuild sorted array by a prefix sum, as this is the part that confused me for a bit, but I actually have finally realized it and I want to help others as well. So, to the explanation. There are two major points why the radix sort works. The first is, on each iteration it sorts values by one digit. How does prefix sum helps it? The idea is that the prefix sum (at the index 7, exempli gratia) is the amount of numbers whose last digit is less or equal to 7 (say this amount is 4). And the prefix sum at the index 8 shows the amount of numbers whose last digit is less than equal to 8 (let it be 6). So in a sorted by last digit array the indices 0,1,2,3 would be occupied by numbers with last digits less or equal to 7, which clearly means that indices 4, 5 would contain numbers with their last digit equal to 8. I really liked this trick, thank you for showing it to me. The second part of radix sort is it's stability, but it's trivial compared to the witchcraft above.
@@Darkev77 He was talking sbout the linked list approach, with the downside of the overhead. I was picturing how to layout the datastructure in an array, remembering how a heap is actually stored in an array. The problem is to know where to start each of the buckets. At this point is where I noticed the sums are the index of the pointers to each bucket 🤯. So he solves the allocation problem.
For people starting: The first algorithm as expressed does comparison, but not between the elements but between the numbers and the values on the array. The kind is “is it a 1” the reason he says correctly no comparison is because he has the implementation in his head. Like this m[n]+=1 where m is the count vector and n is the element in the input array. So yes it’s lineal. Notice that this is the case vaciar we are exploiting the nature of the data.
Don't know why youtube recommended me this, but for once the algorithm got it right! Didn't know i wanted to know this. Perfectly explained, great step-by-step examples. Thank you for the content
If you subtract one from the first element when building the prefix sum(making sure to use a wrapping subtract to avoid overflow(unless you're using signed numbers), it should remove the awkward -1 for each step.
It wasn't explained very well in the video, but you are actually subtracting 1 from that digit's prefix *each* time you copy a value from the source array to the destination array. Let's say your original array has three "5"s, and the starting prefix for that digit is 9. The first time you add the "5" to the destination array, you subtract 1 from the prefix, placing it at index 8, but the 2nd time you add the "5" to the destination array, you subtract 1 AGAIN from the prefix, making it index 7, and so on.
For computers, might be more sensible to use binary counting system for the bucketing so, you can use the speed of faster bit-shift and bitwize operations for the bucketing -if used with signed/unsigned numbers, and not with 2's complement numbering system
Radix Sort is basically a quick sort with a base greater than 2 (quick sort is a radix sort with only 2 different radices: those elements below the pivot and those above)
Also one thing worth noting is for input numbers with lots of digits, it takes some time and processor power to extract each digit. Also for very long numbers like 32 bit, which can be as high as 4,294,967,295 using standard binary encoding, that is a lot of passes you need to make, 10 total on each.
I think for 32 bit numbers, you’d usually only consider 8 bits at a time so 256 counters and four passes would do it. Nobody would consider sorting 32 bits numbers in decimal. It just makes no sense when bytes are easily extracted.
Excellent ideas! I've wanted to cover heaps and tress for long time! No idea when I'll get around to it tho... Thank you for the suggestions and thank you for watching :)
Some thoughts... We can optimise this for "ragged" lists. The difficulty of ragged lists may not be immediately apparent in the video as all the numbers have the same length... but... If you imagine a list of 100 items where 99 of the items are small double digit numbers... and just one of the items is a huge 100 digit number, we notice something isn't quite right : We realise that we're making 100 passes of the entire array, when it really isn't needed. The vast majority of the array is actually effectively sorted after just 2 passes! This means we should recognise three things... 1) When there are no more remaining digits in the number we're processing, it's done! It can be finalised into the low end of the final output array with its similarly short friends. These numbers need no more processing... so, by swapping these off to the left, on the next pass we can iterate through a subset of the array (the high end) These finalised numbers could also be written into the results array after each pass (1 digit numbers, followed by 2 digit numbers, etc) ... In threaded architectures, this means that the consumer of the list (which may be another thread) can begin consuming the list before it is even completed ... for example, writing it out to a disk or passing it into some other function that takes numbers in sequence. 2) Numbers that are finalised (see 1) no longer need further processing, so our subsequent passes could be much shorter. We still intend to do 100 passes, but the work required is much less as the list is considerably shorter after each pass. The list can be shortened by swapping, which keeps the items that require further processing together - something that only provides a speed boost with very ragged lists. Swapping the current completed number to the left side of the array means that we can treat the array as being one element shorter. The next completed number can be swapped with the next leftmost position ... till all completed numbers are on the left side. We can them continue processing ONLY the numbers of the right side (the numbers still requiring work) ... as if the array were a shorter one. 3a) We also know that if there is only one number left unfinalised, it doesn't matter how many passes it still needs - its position has to be LAST. So, in the case above, we ARE finished after just 2 passes - even if there's still a 100-digit number left. (1 digit lists are not sortable) 3b) We can extend point 3. If there are only two numbers left and they require more than a single pass to figure out, we can do a simple comparison instead, as two numbers are always faster to compare directly. 3c) Indeed, this strategy is also valid for FAR MORE than two remaining items. If a list is particularly ragged or has very large outliers, then a strategy that tells us when to switch to a comparison sort would be useful. If we know how many passes and elements remain, we can quickly decide when it makes sense to abandon radix sorting and switch to a comparison strategy for the remaining elements. For example : Imagine there are 95 single digit numbers and 5 one-hundred-digit numbers... this is VERY ragged In such a case, 95 of the numbers are finalised in the first pass, and fill up the first 95 positions of the final array. But does it make sense to make 99 more passes of the five remaining digits JUST to sort the last few numbers? No ... we can make a quick set of comparisons and write them into the last few positions FAR quicker than we can radix them. In real life, data can be quite ragged. So, it makes some sense to consider the distribution of "lengths" and decide some metric for when/if to switch strategies... in fact, you should do this (look at your data) whenever choosing an appropriate sorting strategy. There isn't a "best way" to sort ... it all depends on your data. So, knowing what your data actually looks like is very important : / Case 1: if you are selling used cars, the lengths are unlikely to be less than 3, or more than 5, so there isn't much variation. The added complexity of dealing effectively with 'ragged' lists are unlikely to speed up the sort and will almost certainly just slow it down. Case 2: Bank balances could range from single digit penny values (the cash poor/abandoned accounts) to more than twelve digits (large companies) ... and so, the list is going to be VERY ragged. There is probably a concentration around 3-4 digits. The time saved in not subjecting every number to a large number of passes makes the additional checks for ragged lists worthwhile. So first, know your data : ) It would make sense to profile your data and look at the distribution of lengths (in the radix required) to understand how much duplication of effort would be involved when using the naive radix sort. Then consider whether to employ any of the early or late strategies : - Late strategy : If the outliers are large and relatively few, then switching mode (near the end) to a comparison sort would be highly advantageous. - Early Strategy : Where early removal / finalisation of a large number of shorter items would significantly reduce the length for the remainder of the radix short, this will have a huge impact on the sort time. It will be worth shuffling completed items to the left, and reducing the pass length. And, know your data consumer... - Asynchronous strategy : When a consumer is sat waiting, when they could be processing - use the 'early strategy' to start sending data AS you have it. This will stop your application grinding to a halt whilst you finish sorting. So, consider where the data is going. If the consumer of the data could start working on it straight away, before the sort is actually complete - then the "early/asynchronous strategy" can avoid everything grinding to a halt whilst you sort by making early results available as soon as you have them. This is an important consideration in modern multithreaded systems... or when writing to disk, etc. Don't worry if you didn't understand any of that - these are more advanced strategies that can be used when facing large sorting tasks in the 'real world'. It's worth thinking about them once you're comfortable with sorts... but they're not worth stressing out about if you're new to sorting ; ) Who am I kidding ; ) Most coders will end up using Array.Sort(data); and not caring how the job gets done ; )
Great explanation! Thank you! One small remark. Unfortunately, by adding some offset to float and then substracting the same value you will not end with original float value. Even more, adding offset to some float values can make them indistinguishable.
The linear sort was used for keypunch card sorting. It was done by setting sensitivity needles to set the iterations of sort. This was a mechanical sort controlled by an operator, every iteration was set by a human, every iteration. In total 80 full sorts passes were required because each keypunch card had the potential for 80 iterations. Each pass would sort one column at a time. Very time intensive and God forbid dropping a tray of keypunch cards during the sort, everything would have to be redone. When you need to sort hundreds of thousands of keypunch cards you don’t want to make a single mistake.
@@dale116dot7 True , however the user data stored on Keypunch was a different matter due to volume and linearity of the user data sort. The sorter you’re referring to was usually a tabletop model, the bigger ones were floor models with 80 card collectors per sort. One column at a time for all the cards. Rinse repeat after moving needle, collect, do not drop tray, or start from square 1. Trays were 3 feet long and there were hundreds of trays.
Can be used on variable length strings too. numbers are just strings with just two counts (0 & 1) Short cut too: if you run out of digits have a extra count to indicate 'already sorted' and treat like -1.then you can skip all the items in the next round (bin) that was -1 (character strings go left to right,numbers right to left)
Some clarification: 6:35 "Hey presto, we haven't got anything sorted at all" (after the first pass). This glosses over the important fact that at the end of the first pass, the last digits *are* sorted. Indeed, each pass sorts the whole list via the digit being scanned in that pass. Another key feature that should be mentioned is that the method of stacking the buckets preserves the order the numbers were already in, and thus preserves the lower-digit ordering(s) imposed by the earlier passes even as you're sorting the new current digit. And so does the method of unstacking the buckets back to the output array. Without this, each new pass could scramble and lose the low-digit ordering imposed by the previous passes. But with it, the final (highest-digit) pass is guaranteed to leave everything in a fully sorted condition, since it preserves the already-ordered runs of the lower digits. This property (of preserving the prior ordering of same/bucketed items during a new sort) is called "sort stability", and is very useful when constructing multipass algorithms. Meanwhile, most efficient sort algorithms are "unstable" and don't guarantee preserving any prior ordering. For example, if you quicksort a list of employees by name, and then quicksort that by sex, the resulting list will have all the males together, but their names will likely end up scrambled again. But if you use a stable sort algorithm and do the name sort followed by sex sort two-pass process, the guys on the final list will still have their names alphabetized.
Incidentally, you can do a "stable" sort even with an "unstable" sorting algorithm by including the item index number in the comparison key. In the above example, don't just sort employees by "sex" on the second pass, generate temporary "line numbers" for the alphabetically sorted list (1 for first item, 2 for second item, etc.) and then sort by "sex"+"line number". (In this simplified example, you could of course just do a one-pass sort on the key "sex"+"name" to get the job done, but most cases of multipass sorting aren't so easily collapsed, and that's where stable sorting and the line-number trick become quite useful.)
Radix sort is exactly how punched card sorters worked in ancient times. The machine had a bin for each punch position. (There were 12 punch positions in each column.) The card deck was run through the sorter once for each digit position, and the bucket contents picked up in order, the deck restacked, and run through the sorter for the next punch position until the entire sort key had been covered. Sorting a couple of thousand cards could be done quite quickly.
astonishing!
Such equipment went by the name Unit Record Machines. This category of hardware included sorters, simple calculation tools (adders, multipliers, subtracts and dividers, for instance) and printers.
Bucket sort at work being efficient !
I worked in a clearing bank in London back in the '60s and we used the same technique to sort cheques by account number, by magnetising the digits on the cheques and reading them. Eight passes for the account number which also sorted in branch order. The cheques had already had anything other than those that belonged to the bank removed and sent to the other bank. London cheque clearing in action.
Those were the days!!!
A few years ago I was working on a project to create a bounding volume hierarchy for collision detection, and as part of organizing the objects (along a space-filling curve for efficiency's sake) I followed some technical papers to create a GPU-based, parallel binary radix sort. It was fast, and the particles that were being collided never had to leave GPU memory. But it was a right beast.
That's why I'm here, octrees!
It takes a highly specific kind of nerd to call that awesome, but god damn, that is awesome!
Decrementing the prefix sum serves two purposes: 1) converting to a zero-based index, and 2) avoiding collisions in the output array. The latter is accomplished by updating the value stored in the prefix sum array. This is a crucial point that should be stated explicitly.
You are right! Thank you for watching :)
I was confused at first, but the visualisation made it really easy to realise you can just increment the counter!
I've seen many youtube videos and papers on this matter and I must say that I never have seen sorting algorithms explained so simply and with such passion!
I really liked how you explained the logic behind comparison based sorts on part 1, it's really useful to understand sorting networks and their limitations.
You are an excellent teacher and hands down one of the best youtube channels on this matter!
Btw, just a note: to implement radix sort for signed integers you just need to do the prefix sum in the last digit that includes the signed bit in a different order, going from the middle of the array to end and then from the start to the middle again so that the digits starting with
1 (the negatives) appear first.
For floats the idea is similar, but instead, you also have to do the first partition of the prefix sum in reverse order (going from the end of the array to the middle, and then from the start to the middle again) and then you adjust the scattering part so it decrements the pointers corresponding to numbers from the first partition. There are also bit flipping solutions, so you don't need an extra radix pass.
Just have counts from -9 to 9. Eg 19 counts
@@Wyld1one it won't work, we start from the once's place, if you want to do -9 to 9 i'll add some overhead such as add +9 to your counts etc etc, and would also have to check the -ve every digit cycle
This is literally the only channel on youtube about programming that i watch solely because the videos are made so engaging and fun, and not because i have to prepare for test.
Best channel
I’m just a random 20yo student and I discovered this channel out of YT’s algorithm
Loved it after only one vid, subbed and have been binge watching this on this rainy sunday afternoon, sipping coffee.
My life is pointless but at least I’m learning cool stuff
Hey mate, your life isn't pointless! I found this channel last night, and it's been great. I "graduated early" with a 2-year degree in electrical engineering a long while ago, never used it outside of school unfortunately.. and today I'm employed as a full stack dev with 7+ years of professional experience in that position. Life can be crazy, and I don't know much about it (yet!), but I know for sure, your life isn't pointless :) This is an old post, but hit me up if you wanna chat, or have any questions about anything. Much love.
if you "really" learn this, by which I mean you understand to the degree that you can explain it to others well by yourself, you are already on track to a great career as a good software engineer. In time, you'll build yourself a good career at a software company like Microsoft or Google. Regardless of whether you like the companies, you'll at least set yourself up for a good salary which'll enable you to do what you like. Keep it up!! - source : I'm a senior software engineer at Google myself.
Cringe
linked lists take a lot of memory
me a python programmer:
i have never heard of that guy
me, a Java programmer {
you missed the braces and semicolons;
}
@@jacknguyen5220 I doubt you are a Java Programmer... There is neither a class declaration nor any method indicator ;)
Meanwhile, in Perl: !#$%&(%$%^#@#%&%^@#*
Haskell: wait, there's an alternitive?
me, an assembly programmer: what's a list?
Radix sort is truly a sort without comparison.
Get it? Because Radix doesn't do comparisons
Like discrete mathematics is the one that counts the most
Glad *that's* sorted!
I see what you did there
Now, there's a time and a space for this sort of thing ...
Your energy and accent remind me of Steve Irwin!
"Crikey! It's a radix sort! Now, we'll just sneak up behind heeeem and grab heeeem behind the head....... "
Cheers from New Zealand!
That hit close to the heart . . . XD
MIND. BLOWN. Never have I been so sad that my sorting list is short. xD
This year has been really nerdy for me. I learned Python, Java, and i'm watching this awesome series!
That's awesome good for you
I code in c++ and whole life is nerdy)
Awesome, you should try c, c++ and your cpus assembly language to see what goes on under the hood
@@davidlynch4202 I am learning C and C++, but x86 assembly is way out of my scope right now.
@@bluesillybeard thats what i thought too before I started trying to learn it :P you could figure it out
10:36 “0 to 9!” That’s quite the range for the array 😉
That's a fact ...
... orial
some amps even go to 11 !
Ok, this just randomly turns up in my YT feed for no apparent reason, even though it's old and I haven't watched a coding video in literally years. But thanks, algorithm, for knowing me better than I know myself, because I loved it!
Seriously Mate, your this series ... I am a CS Student of 3rd Semester. We haven't started Data Structures and Algorithms yet, but will soon be (from 15th of Sept). And I am feeling so lucky, that you are making such a Great Series of videos based on Algorithms! This Counting and Radix Sort got me curious to understand all types of Sorting and other Algorithms. All Thanks to you mate :)
Was blown away by count sort. Simple yet genious idea. Thanks for this video.
Right after I graduated from university, I did some travelling and ended up doing odd jobs at a travel tour company. It happened to be the end of the fiscal year and given that this was more decades ago than I'd like to admit, they had a mountain of physical files that needed sorting. Usually they spent 2 whole weeks to sort the files. They asked me to sort it. I can't remember exactly how I set it up, but I took over several desks and made my "buckets". Bucket sort works *really* well with physical files because concatenating them back into the original pile is simple :-). I got it all done in an afternoon and after that they thought I was a genius :-D
seriously. when someone hands you several file cabinets of paper, the first step is to sit down and think.
The complexity of the Radix Algorithm is dependent on the size of the largest number. So if you had just one max value 64bit integer, you would be running the counting algorithm 19 times.
Not really. If you do MSB radix sort it is perfectly possible to skip empty buckets and buckets of size one.
As usual, real performance depends on implementation and data distribution.
Nothing stopping you from using 100, 1000 or 10,000 counters. Gets you down to ten, seven or five passes. 22 upvotes for you, but not a single bright bulb in the crowd for two years - yikes!
No? Bc you will quickly run out of memory
@@jacey0479 You are mistaken. Why do you think memory will be exhausted?
Your counters have to be < the size of the list. That is the problem with Radix sort, trying to find a balance between memory allocation and speed. Obv it also isn’t good for small lists.
Radix sort is O(d * n), where d is the length of the elements. For sorting elements whose length is shorter than log(n) radix sort absolutely blazes through the list. If sorting a list whose elements lengths are longer than log(n) radix sort actually performs worse than its contemporaries. Given that a randomly generated list of unique packed keys has a longest length of log(n) (you eventually run out of unique elements at any given length and have to add another digit), the d * n starts looking suspiciously similar to nlogn.
However if you have a very long list of short, non-unique keys (if you wanted to sort a list of dice rolls or something I guess) this is absolutely the best way to do it!
If you have to sort a list of dice rolls, Just count them in an array of 6 bins. This will most likely be faster than radix. If for some reason you want a long list instead of a compact array with the same information, you can always generate it from the bin array in O(n) time
Your enthusiasm for sorting algorithms and computing in general is really engaging.
This is like the big interview you get after winning a championship, perfect!
Nice video, but I have to complain about the supposition that radix sort is somehow O(n). Its extremely important to leave in the O(nd) where d is the number of digits.
O(n) invites an extremely dangerous line of thinking where somehow people may come to the conclusion that radix sort somehow asymptotically beats nlog(n). It does in an extremely limited sense but its hardly the full story.
Unless you have an exponentially increasing fraction of duplicates, then d must be of the same order as log(n). You can't represent 10,000 distinct numbers without at least 5 digits or ~log2(10)*5 = 15 bits. Suppose you are infact beating those bounds and d < log(n). Then at most (base^d/n) fraction of your array can be unique values by the pigeonhole principle. Concretely if you are beating it by 2 decimal digits or like 6.6 bits then at most 1% of your array is unique an the other 99% must be duplicates.
Plus it makes it seem like log(n) is much faster growing then it is. In practice log(n) is strictly less then 64 on most machines. Its really not fair to make a "fixed word length" argument for radix sort and other comparision sorts because in reality you could never sort more then 2^64 elements on a machine with 64 bits of address space anyway.
Hello, I've got to agree and disagree. I hope that Mr Creel will talk more about the complexity in later videos, but I'd like to point out that the time complexity of Radix is actually *O(log[base b](k) * [n + b])* , or if you prefer *O(log(k)/log(b)*[n + b])* , where *b* is the number of _bins_ in the counting array (10, in our case), and *k = 1 + max_element - min_element* . Note that *b=10* was used in the video for _simplicity_ but its value should be dependent on the array input.
If we set *b=n* , then *O(log[base b](k)*[n + b])* becomes *O(n*log[base n](k))* . We usually abbreviate *log[base n](k)* to *d* , but as you can see, how we count the number of digits changes as the input size grows.
Informally: As the input size grows, Radix becomes increasingly insensitive to *k* even if *k* grows polynomially with respect to the size of the array.
Radix is a bad choice when *k* is high _and_ *n* is small; specifically when *k > n^log(n)*
I’d say you are both right! The proper time complexity is O(nd). Keys are often fixed in size. Not always, of course, but often. We tend to use 256 as the radix, resulting in 4 iterations with 32 bit unsigned ints. So, it’s true that radix sort’s time complexity is more subtle than O(n), but it’s also true that in practice it tends to perform at about O(n).
I’d add that the time complexity for many things is subtle. Addition, for instance, requires O(1), so long as you have a machine that has an Add instruction with an arbitrary number of bits. Otherwise, it’s O(n) with n being the number of bits. Measuring the performance of algorithms is deep and complicated.
Thank you for the info, and thank you for watching :)
And this is why I generally use big O notation for making quick estimates, but not as a final decision maker. It's a very coarse measurement.
@@elliott8175 that is correct, i found your comment right after explaining the exact same thing in mine. In O((n+b) log k / log b) each value can become a bottleneck. Sure, most of the time N will bottleneck, but so can higher than optimal base and higher than optional range. Especially when sorting binaries, fixed point floats, strings, etc.
The way he explains radix sort... yes his version is not linear. In real radix sorts you always go most significant bit first. This means that after the first iteration you have a mostly sorted array and boundaries for all unsorted portions so you can recurse and sort the sub arrays or switch to quick sort in the subarrays. Aka burstsort.
I love the way you present yourself and talk about these subjects. I've learned great things on this channel that I didn't even ask to learn, but just watched for entertainment xD
I love watching those animated sort algorithm demonstrations, and Radix sort was always one that looked neat... but your explanation is fantastic! I finally understand it, and goddamn, is it freaking clever! :D
Best channel on youtube hands down
I think I am in love with counting sort
Awesome stuff.
Around 15:30, when talking about how to apply the prefix sum, I was thinking of the interpretation that the prefix sum is the running total of numbers with lower digits. So in the first iteration for 721, which end with 1, you are looking up how many items end with 1 or lower. And for 779 you are looking up how many numbers end with 9 or lower, etc. For each number, that tells you how many elements that need to be placed before that number, which also tells you the index of where to place it.
absolutely beautiful, human ingenuity at its finest
one thing that you can take advantage of in some languages is using something other than strictly an array for counting, so you can just leave holes where there are no items with that value, rather than having a bunch of memory full of 0's. unfortunately it's usually slower because these data structures have more overhead than arrays do.
This is an great idea! I think it would be especially useful for Radix Sorting smaller arrays. If we didn't need to Zero the entire digit array each round, might save some time! Cheers for watching mate, and cheers for the info :)
I'm not so sure. I don't know of any random-access data type that you can iterate over (for providing the solution), without having these "holes". We could provide a second mapping array, but this requires a sort to know how to get the right mapping (circular dependencies).
Whether it's possible to sort in linear time is still an open question. Radix comes really close, but isn't actually linear. If we were able to use an array "without the holes" then I think we'd have solved this famous problem and be rather famous (among CS geeks) - so my guess is the appropriate data structure doesn't (yet) exist.
@@elliott8175 I was thinking you might be able to do that with a hash map, but it would require a special hashing algorithm that not only produces semi uniqueness, but ALSO internally stores larger keys after smaller keys, which is the bit we are missing. Maybe a fancy hash algorithm that tweaks itself on the fly in response to the data and performs some acceptable amount of rebalancing yadda yadda. Obviously I dont know the answer. It could also end up that just computing the hash is slow enough that it kills the idea.
This has become one of my favourite comp sci channel. And this is not a small achievement, given the number of great resources on youtube.
Seems like radix-sorting strings would work too, as long as they are made from a defined alphabet?
Indeed it does! A viewer from the last video mentioned he did a talk on implementing Radix Sort for strings at JuliaCon last year! His talk can be viewed at: th-cam.com/video/C65vYWeN7-k/w-d-xo.html
It's actually potentially much better with strings because comparisons can take a lot of time with strings, but accessing a single character is fast.
The bad news is you probably can't make this work with unicode easily. A string comparison in unicode is already an unsolved problem so you may not care about that.
@@meneldal You don't need your string comparison to be particularly meaningful to use it in a sort. You just need it to be consistent.
@@vylbird8014 The problem in Unicode is two string can look identical when you render them but don't have the same representation. Even normalization doesn't deal with every subtle thing.
So while it will be consistent, it may give you results you don't want.
@@meneldal You just need to transform your Unicode strings into byte strings such that the desired ordering is preserved. For example, the C standard library includes strxfrm() and wcsxfrm() for exactly that purpose.
I discovered your channel like yesterday, and as a game programmer in training I love your videos, you always explain things perfectly. Keep up the good work
I love you my guy
Ha! You too
Same, this series is so interesting
It makes perfect sense as you explain it. It reminds me of when you sort by multiple fields, you do the most important last.
Very informative and easy to understand! I think it was well-paced for beginners, as well as for people to whom the particular topic is novel, but the concepts familiar.
Beautiful content, Thanks for the amazing explanation and visuals, it's clear that you love what you are teaching and that makes the videos more than perfect
10:41: "We've got the input list just here... same elements as before, I think..." "Well, you wrote it, mate!"
=)) What's a Creel playing both the teacher and the student for our amusement.
Question: for integers, if you know you're big-endian, isn't it easier to simply build the counter array to have power-of-two buckets (like 8 or 16) ? And then, instead of doing mod 10, simply read the relevant 3-4 bits, put in the relevant bucket, and so on. You also have to make sure to have the sign bit in it's own step. Also, would it help to construct all the count arrays at once, so you only traverse forward the array once ? It uses a bit more memory, but arrays of 16 integers... doesn't sound that bad. Worst case for normal integers would be to compare 64 bit signed integers, and that would amount to 64/4 + 1 = 17 count arrays (the extra one is for the sign count array).
Cheers!
Sry, just realized I replied to the wrong comment yesterday, haha! My response didn't make any sense. Anyway, thank you for watching :)
@@WhatsACreel No, it made sense. Having ANDs instead of DIVs (well, mod by 10 I think would've been for taking the digits in base 10)
@@WhatsACreel Performing AND on LS 4 bits, then AND on MS 4 bits with SHR to bucket count and sorting process used on byte size numbers ! If needed, Scale up by groups of 4 !
I was puzzled at first, but the final part of the video cleared it up for me. Brilliant algorithm.
I know what you mean! It's such a clever trick! Cheers for watching brus :)
Great video series. Radix getting the attention it deserves!
I would point out though that I don't think that Radix is a compromise between speed and memory (when compared to Counting Sort). If k is (1 + max_element - min_element), then counting sort has O(k) space complexity **and** O(n+k) time complexity (auxiliary array requires linear traversal: first to initialise to 0, then to load the solutions). This is just as much of a time problem as a memory problem, so Radix helps to handle both of these.
You're a natural! Nice and concise and clear! Kudos for that!
Tell me you're a high school, college, or university teacher!
Back in the day, I encountered a radix-2 sort that was coded for a PDP-8 with two LincTapes (or DECtapes, which were just LINCtapes rebranded). Random access tapes - there was a timing track so that you could read and write anywhere, not just at the end of the tape. The buckets were accumulated in odd- and even-numbered sectors on the output tape. There was a weird trick where alternating passes through the tapes read the tapes backward. Nothing like sorting a megabyte of data on a machine with 16 kilobytes of core memory!
When I jot a job as a mainframer, I encountered five-tape read-backward polyphase merge. Insane!
Man.. The things youtube wants me to learn is amazing... Thank you for taking the time to make this topic clear, understandable and interesting.
well strictly speaking, it's not O(n). it's O((n+b) *log k/log b), where k is the largest number you're sorting and b is the base of its integer representation. because of this, it might be better to use base-2 representation to minimize b term or to use base-10 or even something like base-256 representation to maximize the divisor.
so assuming that k and b are constants is not always precise, because you might actually want to change them to make the algorithm run at maximum speed.
Right you are! The third video shows the code and performance of a base 256 Radix Sort! I agree that the performance is logarithmic when sorting data or arbitrary lengths. It's only O(n) when the length of the keys is fixed. Cheers for watching anywho, have a good one :)
I would call it O(N log R) where R is the number of bits. No need to change base as that is just a constant that gets simplified away by the definition of Big-O
But I agree that it's not fully honest to call it O(N).
Okay, this is awesome! I've been trying to figure out a smart way to implement Radix Sort for a while, and you just gave me a way! Thank you for the awesome videos, keep doing awesome!
No worries mate! Links to the original sources as well as my own version of the code will be provided in the final video. I hope to upload it later today. Thank you for watching :)
Hearing "Good stuff!" takes me back to 2014-2015 :D
I have a large array been waiting for this sort
Did not see other videos from this channel yet. But this one is enough to be subscribed! ))
Right now I´m studying "Computer Science" and i am learning for something we call "Algorithms and Datastructures". These 3 videos were actually shorter and way better than the ones from university. I can´t find something for big O notation in general from you. Do you have Videos for that topic? Anyway i reallly love your vids! Keep on Doing these! And sorry for bad english.
Your English is great! I don't have any vids on Big O, but that's a great idea! Thank for watching, and thank you for the suggestion :)
Wait ... For Big 'O Notation, you can check the channel of : *CS Dojo* . When "What's Creel" said about Big 'O notations, I instantly jumped to his tutorial :), and got the concept. Then came here to understand this. By the way, Great explanation.
@@WhatsACreel caaan you make big 0 video sir covering topics from CLRS bible..I am not able to understand that book.
Download EDX app on your phone and do the CS50 Introduction to Computer Science from Havard.
Aachen? x)
Watched the first video and was going to propose what you called "counting sort"; my idea was to determine min/max and only use counts that fall in that range.
I;m old enough to remember how the old IBM punched card machines were used for sorting. It was a radix sort, and the "buckets" were actual buckets or slots that a card would fall into, if, say, column 35 were punched with a 3. You'd then gather the 10 buckets up in order, and run the deck through again, soring on column 36 (or whatever).
What an underrated channel!
Just watched the first one, nice job posting the second part so quickly
Radix sort is plain magic, and youve explained it perfectly ö
Amazing mini-series! Thanks a ton for taking the time and effort to make the beautiful presentations. Much appreciated. And, on a different note, is that a cat holding a cricket bat? I'm talking about the picture behind you.
You did such a good job explaining this! I’m just a self taught programmer but i had no problem understanding this! And it’s really interesting too!
thanks mate i appreciate your approach to these videos. you are very human and i can really get a feel for the worth / importance of each thing you mention. thanks man
That was a really neat explanation of a smart sorting method. Thank you for sharing.
Please do a video on how Radix Sort performs with differently based numbering systems, like binary or hex. I'd assume larger based numbers rely more on storage and read/write speeds, and smaller based numbers like binary rely on processing speed instead. Thank you!
EDIT: Sorry, didn't see the other video you posted. Watching it now!
awesome stuff! also you're really good at explaining all this, it's all so simple to understand compared to some other explanations out there, awesome work!
Brilliant, and such an awesome explanation. Only improvement would be to mention to subtract 1 from the prefix sum for *each* time you move an input to the ouput, not only once (all the talk of moving from 0 to 1 base counting confused that part for me). Slow-mo'ing the part where you go through the rest of the items real fast helped me see what you where doing to make it work. Thanks for sharing!
An alternative approach would be to shift all the counts to the right and set the count of 0 to zero. In this approach, you would iterate from left to right and increment the counts instead of decrementing them. You would not have to convert between base 0 and 1 in this approach.
An excellent explanation and demo of radix sort. Quality TH-cam content this is.
I agree, very clearly explained. After watching this video, (plus the previous videos reference to a mask and right shift) I wrote a working 16 bucket radix sort in 10 minutes.
One of the best sorting videos I have seen so far. Great work!
This is a man who loves it.
Thank you youtube algorithm, it has decided that I needed to watch this today, and it was right.
Thank you man.
I discovered radix sort in this crazy guy videos that make animated sorting algorithms with sound, and it's a lot of fun to watch, but not I finally understand how it works. It's a kind of magic ;).
You sorted it clearly in our brains !!!!!!!!
The "bucket" version of radix sort is exactly how you sorted cards in an old mechanical punch card sorter. It took as many passes as there are digits. So you had to pull the cards out of the output stacks and stack them up in the input.
Programs stored on punch cards would often be numbered in steps of ten in the last 8 columns. This way to insert a line after line #1000 of a 100 card stack, you would number the new card as 1001.
If you go with 16 counters (AKA 4 bit digits), the counters can be on the stack. On most machines, allocating 16 words of stack takes no extra time at the routine entry.
Sorting strings of text or other large things can often be more efficient if you make arrays of pointers.
That's right! I forgot about that... anyone who ever dropped their program card deck (or who's wise cracking buddy gave it a toss) but was wise enough to put line numbers on the cards knows all about this.
@@rhymereason3449
The new discussion of it is sort of an "everything old is new again" thing. The cards were invented for the US census before computers were machines. The mechanical "tabulator" let the government work out how many plumbers owned cats without any electronics needed.
I didn't see you mention that when building the output array, you increment the index in the count array, to handle where the same digit is repeated. The prefix sum has already taken this into account.
Also had to replay a couple of times to understand this, but I believe it's DEcrement rather then INcrement, right? He decrements the prefix sum and the next time the same digit occurs the prefix sum is already decremented and gets decremented once again
@@SergeyNeskhodovskiy yes, and that's also why you move from the end of the array to the start. You move the higher numbers into position first, then decrement so that the next position in the prefix sum is next highest number
This is actually pretty irritating. He decrements the index of each value once it is accessed so that repeat numbers don't land up in the same spot. It's a major omission that will cause people who don't know what a radix sort is.
@@disekjoumoer he certain does mention that you decrement the values in the prefix sum. Do you mean he didn't take the additional step of explaining the second purpose of it?
@@disekjoumoer He does mention that though. I agree he should have made it a bit more explicit, but he *does* say you need to decrement it after accessing it.
I was implementing radix sort by my own and I was surprised when my algorithm managed a total of 10GB RAM (not at same time, of course, but the sum of all allocating and deallocating operations).
To improve it first I tried to do a better approach for bucket vector: instead of allocating 1 extra position by push operation, I would double the allocated size and use a second length prop to measure the vector. After that, I could reduce the 10GB total handled RAM to 400MB.
Watching the video, an idea instantly clicked in my mind when I saw the digit counting array: "I CAN PREDICT THE BUCKET SIZE BY ITERATION!!!!" then I stopped video and did it. Reduced from 400MB to 100MB total handled memory.
You can iterate the input array from the left if you use an exclusive prefix scan instead (add up all the elements up before but not including the slot)
So the overall lesson is: know your data.
The digits of a base-10 number, as well as the bytes or nibbles or even bits of a base-2 number, contain much more information than just x < y. Because every digit (or byte, bit...) is already classifying the number according to some power of 10 (or 2). If you can exploit that, you don't need to perform N log N comparisons. In fact, I think the same technique can be applied to fixed- or bounded-width strings, dates and times, tuples...
By the way, I didn't know N log N came from log N!, that's very interesting. Here's a simple proof I found online (not taking the credit)
Proof that O(log n!) ⊆ O(n log n):
*log n!* = log(1 · 2 ⋯ n) = log 1 + log 2 + ⋯ + log n ** log n/2 + ⋯ + log n *>* ⌊n/2⌋ · log ⌊n/2⌋ ∊ O(n log n)
Therefore O(log n!) = O(n log n) ∎
G'day, matey! Thank you again, here's one for the algorithm ! Btw, loved the little joke between you and the presentation with the same different set of numbers, haha.
Well done, loved the graphic work you put into your videos. Of course, some of the radix sorting can be done in parallel.
Indeed it can, yes! Cheers for watching mate, have a good one :)
When building the prefix sum , if you begin one index offset, (sum in index 0 is 0, second index 1 is sum of 0’s and so on). Then if you iterate from left to right when building the output array, you would place the element in the index specified by the prefix sum and then increment count.
superb explaination! by far the most intuitive explanation I watched on radix sort. Thank you!
I would like to see a pinned comment about repeating digits when decreasing the prefix index... I did not realize that you do not reset the prefix index and "accumulate" the -1 so that identical digits don't get the same spot... I had to go through many comments before I found the answer to that Interrogation...
The rest of the video is really informative, thank you!
Great video!
I'd never looked at how radix sort works under the hood. I paused the video at 16:36 and I started prototyping a radix sort algorithm... And it works! It is even faster than std::sort!
Two points though:
- is there a clever way to know when the array is sorted to avoid unnecessary iterations?
- can this algorithm work with a user defined comparison function?
This is the first time I've heard of counting and radix sorts. I've always assumed that quicksort and merge sort were the fastest sorts. But once you began describing counting sorts I quickly got the idea of how it worked.
Hehe, there's a lot of sorting algorithms that are way faster or have better worst cases than the usually default implementations, but they usually consider the data to be sorted and may require more memory. Quicksort doesn't require any extra memory. Another example of better worst case ("faster big O notation") that works with pretty much any comparable data, that has better worst case, only takes up about twice the memory, easily implemented and understood, is tree sort. Just insert items into a self balancing tree (log(n)), then traverse the tree in order AKA O(n*log(n)). That's a very stable sort, best, average and worst case is all the same.
This was very good. I wish that more had been put into explaining the prefix sum - some of the mechanics were quite obvious and didn't need as much explanation as that did. I know it's a lot of work to do these things so thank you and at least it has given me a question to find an answer for.
ah, Ding! now I get it - after writing that...duh. :-)
Counting sort is much slower for not too large lists with very large numbers than radix sort, because you would have to skip many, many count "0"
That's certainly true! Cheers for watching :)
Thank you for the video, I really enjoyed watching it.
I would want, however, to put an emphasis on the witchcraft that let you rebuild sorted array by a prefix sum, as this is the part that confused me for a bit, but I actually have finally realized it and I want to help others as well.
So, to the explanation. There are two major points why the radix sort works. The first is, on each iteration it sorts values by one digit. How does prefix sum helps it? The idea is that the prefix sum (at the index 7, exempli gratia) is the amount of numbers whose last digit is less or equal to 7 (say this amount is 4). And the prefix sum at the index 8 shows the amount of numbers whose last digit is less than equal to 8 (let it be 6). So in a sorted by last digit array the indices 0,1,2,3 would be occupied by numbers with last digits less or equal to 7, which clearly means that indices 4, 5 would contain numbers with their last digit equal to 8. I really liked this trick, thank you for showing it to me.
The second part of radix sort is it's stability, but it's trivial compared to the witchcraft above.
Wow, this makes a lot of sense. Thanks!
13:24 The moment I realize the GENIUS of this technique.
This is AMAZING
Could you elaborate your insight please?
@@Darkev77 He was talking sbout the linked list approach, with the downside of the overhead. I was picturing how to layout the datastructure in an array, remembering how a heap is actually stored in an array. The problem is to know where to start each of the buckets. At this point is where I noticed the sums are the index of the pointers to each bucket 🤯. So he solves the allocation problem.
For people starting: The first algorithm as expressed does comparison, but not between the elements but between the numbers and the values on the array. The kind is “is it a 1” the reason he says correctly no comparison is because he has the implementation in his head. Like this m[n]+=1 where m is the count vector and n is the element in the input array. So yes it’s lineal. Notice that this is the case vaciar we are exploiting the nature of the data.
Don't know why youtube recommended me this, but for once the algorithm got it right! Didn't know i wanted to know this.
Perfectly explained, great step-by-step examples. Thank you for the content
If you subtract one from the first element when building the prefix sum(making sure to use a wrapping subtract to avoid overflow(unless you're using signed numbers), it should remove the awkward -1 for each step.
It wasn't explained very well in the video, but you are actually subtracting 1 from that digit's prefix *each* time you copy a value from the source array to the destination array. Let's say your original array has three "5"s, and the starting prefix for that digit is 9. The first time you add the "5" to the destination array, you subtract 1 from the prefix, placing it at index 8, but the 2nd time you add the "5" to the destination array, you subtract 1 AGAIN from the prefix, making it index 7, and so on.
8.5k likes with zero dislikes is very impressive. Well done!
For computers, might be more sensible to use binary counting system for the bucketing so, you can use the speed of faster bit-shift and bitwize operations for the bucketing -if used with signed/unsigned numbers, and not with 2's complement numbering system
Radix Sort is basically a quick sort with a base greater than 2 (quick sort is a radix sort with only 2 different radices: those elements below the pivot and those above)
love your videos man, just found you here great work!
Also one thing worth noting is for input numbers with lots of digits, it takes some time and processor power to extract each digit. Also for very long numbers like 32 bit, which can be as high as 4,294,967,295 using standard binary encoding, that is a lot of passes you need to make, 10 total on each.
I think for 32 bit numbers, you’d usually only consider 8 bits at a time so 256 counters and four passes would do it. Nobody would consider sorting 32 bits numbers in decimal. It just makes no sense when bytes are easily extracted.
In the case you run out of ideas for new videos: What about heaps (Min-max heap, Binary heap, Fibonacci heap) or k-d trees?
Excellent ideas! I've wanted to cover heaps and tress for long time! No idea when I'll get around to it tho... Thank you for the suggestions and thank you for watching :)
If you're using a custom allocator then the time to allocate may be trivial.
The bucket-sorting system is EXACTLY how punch cards were sorted back in the day.
Some thoughts...
We can optimise this for "ragged" lists. The difficulty of ragged lists may not be immediately apparent in the video as all the numbers have the same length... but... If you imagine a list of 100 items where 99 of the items are small double digit numbers... and just one of the items is a huge 100 digit number, we notice something isn't quite right :
We realise that we're making 100 passes of the entire array, when it really isn't needed. The vast majority of the array is actually effectively sorted after just 2 passes! This means we should recognise three things...
1) When there are no more remaining digits in the number we're processing, it's done! It can be finalised into the low end of the final output array with its similarly short friends. These numbers need no more processing... so, by swapping these off to the left, on the next pass we can iterate through a subset of the array (the high end)
These finalised numbers could also be written into the results array after each pass (1 digit numbers, followed by 2 digit numbers, etc) ... In threaded architectures, this means that the consumer of the list (which may be another thread) can begin consuming the list before it is even completed ... for example, writing it out to a disk or passing it into some other function that takes numbers in sequence.
2) Numbers that are finalised (see 1) no longer need further processing, so our subsequent passes could be much shorter. We still intend to do 100 passes, but the work required is much less as the list is considerably shorter after each pass. The list can be shortened by swapping, which keeps the items that require further processing together - something that only provides a speed boost with very ragged lists.
Swapping the current completed number to the left side of the array means that we can treat the array as being one element shorter. The next completed number can be swapped with the next leftmost position ... till all completed numbers are on the left side. We can them continue processing ONLY the numbers of the right side (the numbers still requiring work) ... as if the array were a shorter one.
3a) We also know that if there is only one number left unfinalised, it doesn't matter how many passes it still needs - its position has to be LAST. So, in the case above, we ARE finished after just 2 passes - even if there's still a 100-digit number left. (1 digit lists are not sortable)
3b) We can extend point 3. If there are only two numbers left and they require more than a single pass to figure out, we can do a simple comparison instead, as two numbers are always faster to compare directly.
3c) Indeed, this strategy is also valid for FAR MORE than two remaining items. If a list is particularly ragged or has very large outliers, then a strategy that tells us when to switch to a comparison sort would be useful. If we know how many passes and elements remain, we can quickly decide when it makes sense to abandon radix sorting and switch to a comparison strategy for the remaining elements.
For example :
Imagine there are 95 single digit numbers and 5 one-hundred-digit numbers... this is VERY ragged
In such a case, 95 of the numbers are finalised in the first pass, and fill up the first 95 positions of the final array. But does it make sense to make 99 more passes of the five remaining digits JUST to sort the last few numbers? No ... we can make a quick set of comparisons and write them into the last few positions FAR quicker than we can radix them.
In real life, data can be quite ragged. So, it makes some sense to consider the distribution of "lengths" and decide some metric for when/if to switch strategies... in fact, you should do this (look at your data) whenever choosing an appropriate sorting strategy. There isn't a "best way" to sort ... it all depends on your data. So, knowing what your data actually looks like is very important : /
Case 1:
if you are selling used cars, the lengths are unlikely to be less than 3, or more than 5, so there isn't much variation. The added complexity of dealing effectively with 'ragged' lists are unlikely to speed up the sort and will almost certainly just slow it down.
Case 2:
Bank balances could range from single digit penny values (the cash poor/abandoned accounts) to more than twelve digits (large companies) ... and so, the list is going to be VERY ragged. There is probably a concentration around 3-4 digits. The time saved in not subjecting every number to a large number of passes makes the additional checks for ragged lists worthwhile.
So first, know your data : )
It would make sense to profile your data and look at the distribution of lengths (in the radix required) to understand how much duplication of effort would be involved when using the naive radix sort. Then consider whether to employ any of the early or late strategies :
- Late strategy : If the outliers are large and relatively few, then switching mode (near the end) to a comparison sort would be highly advantageous.
- Early Strategy : Where early removal / finalisation of a large number of shorter items would significantly reduce the length for the remainder of the radix short, this will have a huge impact on the sort time. It will be worth shuffling completed items to the left, and reducing the pass length.
And, know your data consumer...
- Asynchronous strategy : When a consumer is sat waiting, when they could be processing - use the 'early strategy' to start sending data AS you have it. This will stop your application grinding to a halt whilst you finish sorting.
So, consider where the data is going. If the consumer of the data could start working on it straight away, before the sort is actually complete - then the "early/asynchronous strategy" can avoid everything grinding to a halt whilst you sort by making early results available as soon as you have them. This is an important consideration in modern multithreaded systems... or when writing to disk, etc.
Don't worry if you didn't understand any of that - these are more advanced strategies that can be used when facing large sorting tasks in the 'real world'. It's worth thinking about them once you're comfortable with sorts... but they're not worth stressing out about if you're new to sorting ; )
Who am I kidding ; ) Most coders will end up using Array.Sort(data); and not caring how the job gets done ; )
Great explanation! Thank you! One small remark. Unfortunately, by adding some offset to float and then substracting the same value you will not end with original float value. Even more, adding offset to some float values can make them indistinguishable.
The linear sort was used for keypunch card sorting. It was done by setting sensitivity needles to set the iterations of sort. This was a mechanical sort controlled by an operator, every iteration was set by a human, every iteration. In total 80 full sorts passes were required because each keypunch card had the potential for 80 iterations. Each pass would sort one column at a time. Very time intensive and God forbid dropping a tray of keypunch cards during the sort, everything would have to be redone. When you need to sort hundreds of thousands of keypunch cards you don’t want to make a single mistake.
Although a common use was to sort a dropped deck of FORTRAN cards so at most you’d have eight passes through the machine to get things back in order.
@@dale116dot7 True , however the user data stored on Keypunch was a different matter due to volume and linearity of the user data sort. The sorter you’re referring to was usually a tabletop model, the bigger ones were floor models with 80 card collectors per sort. One column at a time for all the cards. Rinse repeat after moving needle, collect, do not drop tray, or start from square 1. Trays were 3 feet long and there were hundreds of trays.
Brilliantly explained thank you!
No idea why TH-cam recommended part 2 to me first, but I guess we're here now 🙃
It might be because he explains so well, but the first sort with counting occurrences was the first thing I thought of.
Can be used on variable length strings too. numbers are just strings with just two counts (0 & 1)
Short cut too: if you run out of digits have a extra count to indicate 'already sorted' and treat like -1.then you can skip all the items in the next round (bin) that was -1 (character strings go left to right,numbers right to left)
Some clarification:
6:35 "Hey presto, we haven't got anything sorted at all" (after the first pass). This glosses over the important fact that at the end of the first pass, the last digits *are* sorted. Indeed, each pass sorts the whole list via the digit being scanned in that pass.
Another key feature that should be mentioned is that the method of stacking the buckets preserves the order the numbers were already in, and thus preserves the lower-digit ordering(s) imposed by the earlier passes even as you're sorting the new current digit. And so does the method of unstacking the buckets back to the output array. Without this, each new pass could scramble and lose the low-digit ordering imposed by the previous passes. But with it, the final (highest-digit) pass is guaranteed to leave everything in a fully sorted condition, since it preserves the already-ordered runs of the lower digits.
This property (of preserving the prior ordering of same/bucketed items during a new sort) is called "sort stability", and is very useful when constructing multipass algorithms. Meanwhile, most efficient sort algorithms are "unstable" and don't guarantee preserving any prior ordering. For example, if you quicksort a list of employees by name, and then quicksort that by sex, the resulting list will have all the males together, but their names will likely end up scrambled again. But if you use a stable sort algorithm and do the name sort followed by sex sort two-pass process, the guys on the final list will still have their names alphabetized.
Incidentally, you can do a "stable" sort even with an "unstable" sorting algorithm by including the item index number in the comparison key. In the above example, don't just sort employees by "sex" on the second pass, generate temporary "line numbers" for the alphabetically sorted list (1 for first item, 2 for second item, etc.) and then sort by "sex"+"line number".
(In this simplified example, you could of course just do a one-pass sort on the key "sex"+"name" to get the job done, but most cases of multipass sorting aren't so easily collapsed, and that's where stable sorting and the line-number trick become quite useful.)