Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:08,780 --> 00:00:13,780
High in this video I'm going to walk you through how the counting sort algorithm works.
2
00:00:13,880 --> 00:00:23,780
As you can see right here we have a array and it is a pretty large array of 20 or 30 different values
3
00:00:23,840 --> 00:00:33,890
and each value has a corresponding index so we can see the two is at the zero index 27 at the 1 all
4
00:00:33,890 --> 00:00:34,360
the way down.
5
00:00:34,370 --> 00:00:40,070
And they are not currently in order and we're counting sort is going to do is it's going to actually
6
00:00:40,070 --> 00:00:52,400
use the location of the item and it's going to sort it by placing that value inside of the index location.
7
00:00:52,390 --> 00:00:56,900
If that doesn't make sense don't worry I'm going to show you exactly how it works step by step so you
8
00:00:56,900 --> 00:01:06,710
can see right here the value goes to the two index 27 goes 27 22 goes into 8 goes take in if you can
9
00:01:06,710 --> 00:01:13,890
see I'll hit pause right here and you can see right here the one value actually gets taken.
10
00:01:13,950 --> 00:01:24,980
And into this array we're storing it and it adds it to the location of where the one the one index number
11
00:01:24,980 --> 00:01:25,610
is.
12
00:01:25,610 --> 00:01:27,390
And it stores it right there.
13
00:01:27,440 --> 00:01:31,790
And one thing you also may notice is it doesn't actually store.
14
00:01:31,850 --> 00:01:39,380
If you look at the entire array it doesn't store the value it just stores the count of that number.
15
00:01:39,470 --> 00:01:45,970
So if we add 10 twos then we would have a number 10 right here.
16
00:01:45,980 --> 00:01:47,900
We wouldn't have the number two.
17
00:01:47,900 --> 00:01:53,370
So this is simply a count which is one the reasons why it's called the counting sort algorithm.
18
00:01:53,390 --> 00:01:57,180
So continuing it on we're going to go through the entire array.
19
00:01:57,380 --> 00:02:07,850
And for each one we're going to take the value and place it inside of the index of the corresponding
20
00:02:08,690 --> 00:02:10,980
array that we're sending it to.
21
00:02:11,010 --> 00:02:15,800
And so we're going to take this down all the way down the line and it's a great way to organize the
22
00:02:15,800 --> 00:02:16,580
data.
23
00:02:16,580 --> 00:02:19,310
Now the well this is working.
24
00:02:19,310 --> 00:02:21,020
Keep on watching this one.
25
00:02:21,050 --> 00:02:26,420
It's important to know with the counting sort algorithm that it does not work for all data types.
26
00:02:26,420 --> 00:02:33,380
In fact it actually is usually used more as a subroutine in other sorting algorithms such as radix sort
27
00:02:34,010 --> 00:02:35,150
or sorts like that.
28
00:02:35,150 --> 00:02:43,760
So it's not one for all but it does in certain scenarios it works quite well mainly because it's easy
29
00:02:43,760 --> 00:02:45,160
to analyze.
30
00:02:45,230 --> 00:02:46,670
It only uses four loops.
31
00:02:46,700 --> 00:02:49,640
It doesn't actually use recursion or anything like that.
32
00:02:49,760 --> 00:02:50,810
OK so now it's done.
33
00:02:50,870 --> 00:02:56,570
And so now you can see we're actually going to iterate through this new array.
34
00:02:56,600 --> 00:03:04,130
So you can see we're going to be able to have the values and then here we're going to start incrementing
35
00:03:04,220 --> 00:03:04,850
it up.
36
00:03:04,850 --> 00:03:08,860
So where it was 5 and 8.
37
00:03:09,170 --> 00:03:15,120
Now we have 8 8 8 0 8 so we put 8 there 8 plus 1 is 9.
38
00:03:15,290 --> 00:03:20,210
We changed it to nine nine points arrows 9 9 plus arrows 9.
39
00:03:20,270 --> 00:03:26,030
Once again nine plus arrows nine in the next 15 it's going to be 10.
40
00:03:26,030 --> 00:03:34,470
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
41
00:03:34,470 --> 00:03:36,000
up by 0.
42
00:03:36,180 --> 00:03:46,140
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
43
00:03:46,140 --> 00:03:53,790
counting up and taking the total number inside each item of the array and it's adding in that.
44
00:03:53,790 --> 00:04:00,960
So you'll see when we get to the very top that the last one is going to be 30.
45
00:04:01,080 --> 00:04:08,500
And now all we have to do is take these numbers from the right to the left.
46
00:04:08,510 --> 00:04:14,370
There you go and see this is the final step of the counting sort algorithm.
47
00:04:14,420 --> 00:04:20,630
Once again as you can see this the complexity on this is it's going to be similar to other ones like
48
00:04:21,740 --> 00:04:30,650
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
49
00:04:30,710 --> 00:04:31,510
K.
50
00:04:31,700 --> 00:04:38,540
And so it's a quite a different type of solution and it's the reason why it doesn't work for all data
51
00:04:38,540 --> 00:04:39,340
types.
52
00:04:39,590 --> 00:04:45,710
So as you can see right here we're going and we're actually finding the value and we're associating
53
00:04:46,070 --> 00:04:50,220
that value we can see 11 is going to go to the eleventh index.
54
00:04:50,300 --> 00:04:55,530
It's get take a and then put the 11 at that index value.
55
00:04:56,060 --> 00:05:03,920
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
56
00:05:04,040 --> 00:05:09,540
put 23 inside of that new in that new value.
57
00:05:09,890 --> 00:05:16,400
So as you can see this is not the most straightforward algorithm in terms of the way it works process
58
00:05:16,400 --> 00:05:16,790
wise.
59
00:05:16,790 --> 00:05:25,820
However if you actually follow along and you play with some data and see how it works you'll see it
60
00:05:25,820 --> 00:05:29,450
actually does work quite efficiently for certain data types.
61
00:05:33,970 --> 00:05:37,760
I'm going to pause after this next one and we're going to walk through it.
62
00:05:39,780 --> 00:05:40,300
OK.
63
00:05:40,310 --> 00:05:46,200
So in this one you can see where the value 28 in it was in the nine the nine index.
64
00:05:46,260 --> 00:05:47,080
I'm sorry.
65
00:05:47,270 --> 00:05:47,890
Yeah 28.
66
00:05:47,910 --> 00:05:53,470
So we had 28 here at the index and nine in the original array.
67
00:05:53,670 --> 00:06:03,030
So all we had to do was look to the 28 index of this array and we saw that that was 23.
68
00:06:03,150 --> 00:06:13,080
And so we take the 23 to 23 index of the new Our final output array and we take that 28 and put that
69
00:06:13,170 --> 00:06:15,670
inside of that value.
70
00:06:15,840 --> 00:06:24,180
And so we'll play and go through a couple more and then we're going to analyze it again because at least
71
00:06:24,180 --> 00:06:28,540
for me this was not the most intuitive solution for sorting.
72
00:06:28,680 --> 00:06:33,660
The first time I tried it but after you go through it a few times that actually does make quite a bit
73
00:06:33,660 --> 00:06:34,380
of sense.
74
00:06:42,280 --> 00:06:48,520
OK on this one you can see where the value of 28 again.
75
00:06:48,610 --> 00:06:51,080
And it was at the four index.
76
00:06:51,280 --> 00:06:56,740
And so this 28 we just simply had don't look we only have to look at one item which doesn't really matter
77
00:06:56,740 --> 00:06:57,960
what the index is here.
78
00:06:57,970 --> 00:06:59,590
So we took the 28.
79
00:06:59,620 --> 00:07:07,680
We know that that 28 is going to be representing the 28 Index which has a value of 22.
80
00:07:07,870 --> 00:07:18,630
We take this 22 and go down to the 20 second index of the final array and then we simply dump the twenty
81
00:07:18,630 --> 00:07:20,170
eight value right into it.
82
00:07:20,170 --> 00:07:25,420
So it's that part of it's pretty simple and if you look at this visualization I think it's very helpful
83
00:07:25,420 --> 00:07:33,280
because we're It was 28 that is circled in dark blue and where it's 22.
84
00:07:33,340 --> 00:07:34,690
It's circled in light blue.
85
00:07:34,690 --> 00:07:43,270
So the main thing to know about counting saur is how you take the original value and you have that directly
86
00:07:43,270 --> 00:07:47,750
connected to the index value of your middle array.
87
00:07:47,800 --> 00:07:53,470
The one that you're doing a lot of the processing and the counting on and then you use that index value
88
00:07:53,470 --> 00:08:02,980
to look up whatever the actual value is stored inside of that array element and then that is the index
89
00:08:03,040 --> 00:08:05,850
of the final array and then you essentially swap them.
90
00:08:05,890 --> 00:08:14,880
So where 22 is the value in the array at the 28 index in the final array it's just going to be swapped.
91
00:08:14,890 --> 00:08:22,820
So it's going to be 20 the 20 seconds index and it's going to have a value of 28.
92
00:08:23,290 --> 00:08:25,790
Keep on going down the line of eight.
93
00:08:26,110 --> 00:08:30,240
And we know that goes with value and you put the 8 in there.
94
00:08:32,890 --> 00:08:37,060
Twenty seven a twenty seven point twenty one.
95
00:08:37,080 --> 00:08:38,860
And we note twenty seven goes there
96
00:08:42,100 --> 00:08:44,010
and that's it.
97
00:08:44,050 --> 00:08:45,670
We now have a fully sorted array.
98
00:08:45,670 --> 00:08:56,700
If you look at it we have one twos for eights 11 15 six teens 17 all the way down the line until 30.
99
00:08:56,740 --> 00:09:02,400
So it's perfectly sorted and we used it using the counting sort algorithm.
100
00:09:02,410 --> 00:09:07,790
So this one is one that I did not get this immediately it took me a few times.
101
00:09:07,810 --> 00:09:13,390
And playing around and actually watching the visualization quite a bit so please let me know if you
102
00:09:13,390 --> 00:09:15,760
have any questions with that whatsoever.
103
00:09:15,850 --> 00:09:17,320
And I will see you in the next video.
10877
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.