All language subtitles for 4 - Counting Sort English

High in this video I'm going to walk you through how the counting sort algorithm works.

As you can see right here we have a array and it is a pretty large array of 20 or 30 different values

and each value has a corresponding index so we can see the two is at the zero index 27 at the 1 all

the way down.

And they are not currently in order and we're counting sort is going to do is it's going to actually

use the location of the item and it's going to sort it by placing that value inside of the index location.

If that doesn't make sense don't worry I'm going to show you exactly how it works step by step so you

can see right here the value goes to the two index 27 goes 27 22 goes into 8 goes take in if you can

see I'll hit pause right here and you can see right here the one value actually gets taken.

And into this array we're storing it and it adds it to the location of where the one the one index number

is.

And it stores it right there.

And one thing you also may notice is it doesn't actually store.

If you look at the entire array it doesn't store the value it just stores the count of that number.

So if we add 10 twos then we would have a number 10 right here.

We wouldn't have the number two.

So this is simply a count which is one the reasons why it's called the counting sort algorithm.

So continuing it on we're going to go through the entire array.

And for each one we're going to take the value and place it inside of the index of the corresponding

array that we're sending it to.

And so we're going to take this down all the way down the line and it's a great way to organize the

data.

Now the well this is working.

Keep on watching this one.

It's important to know with the counting sort algorithm that it does not work for all data types.

In fact it actually is usually used more as a subroutine in other sorting algorithms such as radix sort

or sorts like that.

So it's not one for all but it does in certain scenarios it works quite well mainly because it's easy

to analyze.

It only uses four loops.

It doesn't actually use recursion or anything like that.

OK so now it's done.

And so now you can see we're actually going to iterate through this new array.

So you can see we're going to be able to have the values and then here we're going to start incrementing

it up.

So where it was 5 and 8.

Now we have 8 8 8 0 8 so we put 8 there 8 plus 1 is 9.

We changed it to nine nine points arrows 9 9 plus arrows 9.

Once again nine plus arrows nine in the next 15 it's going to be 10.

This is going to be 13 14 14 again and it's going to be 14 for all of these because it's only incrementing

up by 0.

And then on the 22 index that you see at 16 19 and 20 and you as you can see all it's doing is it's

counting up and taking the total number inside each item of the array and it's adding in that.

So you'll see when we get to the very top that the last one is going to be 30.

And now all we have to do is take these numbers from the right to the left.

There you go and see this is the final step of the counting sort algorithm.

Once again as you can see this the complexity on this is it's going to be similar to other ones like

like Quick's or or merge sort where it's o of N log then the complexly this is actually 0 0 of N plus

K.

And so it's a quite a different type of solution and it's the reason why it doesn't work for all data

types.

So as you can see right here we're going and we're actually finding the value and we're associating

that value we can see 11 is going to go to the eleventh index.

It's get take a and then put the 11 at that index value.

We'll see the next one we take the 23 go the 23 index take the 17 from it go the 17th index and then

put 23 inside of that new in that new value.

So as you can see this is not the most straightforward algorithm in terms of the way it works process

wise.

However if you actually follow along and you play with some data and see how it works you'll see it

actually does work quite efficiently for certain data types.

I'm going to pause after this next one and we're going to walk through it.

OK.

So in this one you can see where the value 28 in it was in the nine the nine index.

I'm sorry.

Yeah 28.

So we had 28 here at the index and nine in the original array.

So all we had to do was look to the 28 index of this array and we saw that that was 23.

And so we take the 23 to 23 index of the new Our final output array and we take that 28 and put that

inside of that value.

And so we'll play and go through a couple more and then we're going to analyze it again because at least

for me this was not the most intuitive solution for sorting.

The first time I tried it but after you go through it a few times that actually does make quite a bit

of sense.

OK on this one you can see where the value of 28 again.

And it was at the four index.

And so this 28 we just simply had don't look we only have to look at one item which doesn't really matter

what the index is here.

So we took the 28.

We know that that 28 is going to be representing the 28 Index which has a value of 22.

We take this 22 and go down to the 20 second index of the final array and then we simply dump the twenty

eight value right into it.

So it's that part of it's pretty simple and if you look at this visualization I think it's very helpful

because we're It was 28 that is circled in dark blue and where it's 22.

It's circled in light blue.

So the main thing to know about counting saur is how you take the original value and you have that directly

connected to the index value of your middle array.

The one that you're doing a lot of the processing and the counting on and then you use that index value

to look up whatever the actual value is stored inside of that array element and then that is the index

of the final array and then you essentially swap them.

So where 22 is the value in the array at the 28 index in the final array it's just going to be swapped.

So it's going to be 20 the 20 seconds index and it's going to have a value of 28.

Keep on going down the line of eight.

And we know that goes with value and you put the 8 in there.

Twenty seven a twenty seven point twenty one.

And we note twenty seven goes there

and that's it.

We now have a fully sorted array.

If you look at it we have one twos for eights 11 15 six teens 17 all the way down the line until 30.

So it's perfectly sorted and we used it using the counting sort algorithm.

So this one is one that I did not get this immediately it took me a few times.

And playing around and actually watching the visualization quite a bit so please let me know if you

have any questions with that whatsoever.

And I will see you in the next video.