All language subtitles for 5 - Radix Sort English

In this video we're going to go through a fun sorting algorithm.

Let's say it's pretty popular and very powerful among certain data sets and it's called the reader sort.

It has a worse time complexity of Big O K times.

And and you'll see in a little bit what that means it's a step further than say merge sort of quicksort

which are all big-O and long again and usually and it's much different than insertion sort or selection

sort of which are usually going to be and square.

And so the reason why radix is different is because it uses a lexicographic order which means that it

works extremely well with datasets such as strings or fixed length integer representation such as phone

numbers or Social Security numbers.

It's works very well for that.

And so what we're going to do is actually go through an exercise where you see how it works visually.

So we're going to start off with an array and it's going to be let's go with 3:59

three three.

As for Bandhan riding on this and I'm actually trying out a new tablet.

Five forty eight nine eleven four seventy nine.

And the last one is five.

Forty four.

OK.

So that's our right and first step one what we're going to do is actually go in and look at the first

digit of each one of the numbers.

And we're going to sort it from the lowest to the highest.

So step one right here.

We'll see that 9 111 is our first then we can see 383 is the second followed by 5:44

followed by 48

followed by 3:59 followed by four seventy nine cents.

Yes and that's our guidance.

Okay.

So now if you look down that first column you'll see that it is shorted the first column the digits

are sort.

So that's good.

Now we go step 2 and in step 2 what we do is we actually look at the second digit for each one and except

that we take it in this order.

So we take it in this exact order from step 1 and that is extremely important for us to read it sort

won't work.

So we're going to start off looking at the second digit and right away we can see 9 11 is first again

then we can see it looks like 5:44 is going to be next.

And then 5:48 right after that.

And then we have 3:59

479.

And finally three three.

And now for step three which is my favorite step and read it because it's pretty cool how it all comes

together.

We do the last step.

So the lowest in the last step is going to be 3:59

383

for 79

of 44.

Forty eight and then nine eleven.

And as you can see we have a fully sorted list right here.

And the really neat thing with this is you can see it actually separates out with hundreds.

So each one of them is sorted.

It's not like we just kind of skipped ahead step three where we at you know put 300 first.

This guarantees because we went through and iterated through the each one of the columns here.

So first we started out here then we went here and finally in the third one and what it does it ensures

that it gets sorted with each step.

So that's the sort.

It's very basic.

I will put a link where you can go see the actual code that can implement this I'll put some Peifer

Python code that shows how this runs with a actual program.

So let me know if you have any questions at all on rating's.