Name: 5分でわかるラディックスソートアルゴリズムの紹介 (Radix Sort Algorithm Introduction in 5 Minutes)
Uploaded: 2021-01-14T10:48:47.000Z
Duration: 4 min 39 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

Here's an introduction to Reddick Sort as an example, let's say we want a short disarray off six integers each integer valley ranging from zero through 999 and we want to soar disarray in ascending order so that the smallest number comes first.

The first step that we need to take in Reddick Sort is sorting the given array using counting sort and the keys that we're going to use for that will be the last digit in each number.

So it's as if using counting sword to stone array with the valleys 39063 and three.

In this particular case, and with that, the value that we have with the smallest key, which is during this particular case, will be the first woman in the sordid array on After that, they all the values with the second smallest key, which is three.

So 53 will be the second element on After that 633 on 233.

We're gonna keep going like that on to the very end, and the key thing to remember here is that counting sword is a stable sorting algorithm, and so the values with the same keys in this example 53 633 on 233.

They appear in exactly the same order in the sordid ary as they do in the original rate.

And it's really important to use a stable sorting Oliver them as a subroutine for Reddick sort.

Because if we used on the algorithm that's not stable, it just wouldn't work.

Now, the second stepping Reddick sort is short in this new ray using counting short again with the second last visit in each number as the key.

This time, once we do that, the new sordid array will look like this.

And we're going to repeat the same procedure with this new rate.

And this time we're gonna use the first did it as a key, and you notice that there are some numbers without any number in that place, so we'll just use zero as the key for those numbers.

Once that's done, the whole array is gonna be sorted.

Let's now think about the time complexity off Radek sort.

First, we're gonna define some viable Sze.

Let's call the number of elements in the array or the length of the array and and it's equal to six in this particular case because we have six elements.

Let's call the number off business that we need to represent each number D and we need three desserts here and to represent each number we're using the base 10 system here, let's call that be so B is equal to 10 in this particular case.

Now, remember that in each step off Reddick sword, we sort their way using county sort, using one of the digits as the key on the time complexity for counting sword is big go off and plus que where kay is.

The range of keys that we have for each number on the range of keys in this particular case is 10 or B.

Because the key ranges from zero through nine on.

And so each of these steps takes big oaf and plus be in time, and we need to repeat this procedure three times in this particular case or D times in general.

So the time complexity for the whole algorithm off Radek sword will be big o d.

Times and plus be And this is quite fast.

When the range of input is fairly limited compared to the number of elements that we have India rate.

And in that situation, depending on the size and the nature of the input, it can perform better than on optimal comparison based sorting all over them, such as Quick Sword or MUR Short, which would take big oaf and log and in time.

And one last thing to note here is that there's a range of values that we can choose from for the value of beat.

We chose Space 10 just for simplicity and just to show an example.

But we could've chosen, for example, based 100 based 248 or any other positively dessert for that matter.

And this choice will essentially come down to making a trade off between time and space because the larger value that would choose for be the more spaces record for the county sort step.

 But at the same time, ah, larger, be or larger base will imply a smaller D or less number of digits for each number. 