Name: 0.3 データ構造とアルゴリズム：選択ソート (0.3 Data Structures & Algorithms: Selection Sort)
Uploaded: 2025-01-06T13:33:29.000Z
Duration: 7 min 5 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

Okay, so let's talk about this idea of sorting integers.

では、整数の並べ替えについて説明しよう。

So, I'm going to look at a specific example problem.

では、具体的な問題例を見ていこうと思う。

So, we're going to look at sorting a couple of different numbers, and then we'll kind of build off of this idea and look at sorting more data.

そこで、いくつかの異なる数字を並べ替えて見ます。そして、このアイデアを基に、さらに多くのデータを並べ替えて見ます。

Okay, so for our simple problem, we've got the numbers 89, 3, and 1.

さて、今回の簡単な問題では、89、3、1という数字を用意した。

So we could come up with some sort of an algorithm to try and sort these.

だから、これを並べ替えるアルゴリズムのようなものを考え出すことができる。

So, one of the simplest things we could do is we could just try all possible combinations until we find one that's sorted.

だから、最も単純なことのひとつは、並べ替えられる組み合わせが見つかるまで、ありとあらゆる組み合わせを試してみることだ。

So basically, we could go through every possible ordering of these until we identify one that's clearly sorted.

だから、基本的には、明確に並べ替えられるものが見つかるまで、可能な限りの並べ替えを行うことができる。

So I could start with whatever order I was initially given, and then I could swap two elements.

だから、最初に与えられたどんな順番で始めてもいいし、2つの要素を入れ替えてもいい。

そうしたら、3番をフロントに移すかもしれない。

And eventually, we'll stumble across the perfectly sorted order.

そして最終的には、完璧に並べ替えられたオーダーに出くわすことになる。

Of course, obviously, this seems very, very, very inefficient.

もちろん、これは非常に、非常に、非常に非効率的に思える。

With just a simple problem like this, it was probably obvious to you what the order should have been when you just first glanced at it.

このような単純な問題であれば、最初にちらっと見ただけで、どのような順序にすべきかは明らかだっただろう。

The human brain is incredible at pattern matching.

人間の脳はパターンマッチングが得意だ。

But for the rest of our discussion here, we'll want to think very, very concretely and think about each individual step so we could translate it into code rather than relying on our instantaneous intuition about what the problem should be.

しかし、ここでの残りの議論では、問題がどうあるべきかという瞬間的な直感に頼るのではなく、非常に具体的に考え、個々のステップをコードに変換できるようにしたい。

Okay, our first sorting algorithm seems a little bit cumbersome.

さて、最初のソートアルゴリズムは少し面倒なようだ。

So let's add in some more data here, and we'll talk about a second type of sorting algorithm.

ここでさらにデータを追加して、2つ目のタイプのソート・アルゴリズムについて説明しよう。

So now we're going to take a look at what's called a selection sort.

それでは、セレクション・ソートと呼ばれるものを見てみよう。

So a selection sort is called a selection sort because a lot of the work takes place in selecting a value.

セレクション・ソートは、値を選択する際に多くの作業が行われるため、セレクション・ソートと呼ばれる。

So the way a selection sort works is it's going to try and select the value that belongs in our next available position.

つまり、選択ソートの動作は、次の利用可能な位置に属する値を選択しようとするものだ。

So by that, I mean we'll start off trying to find the value that belongs in the very beginning of the array.

つまり、配列の一番最初に属する値を探すことから始めるということだ。

Once we've found the value that belongs in the beginning of the array, we'll move on and we'll try and find the value that belongs in the second position of the array.

配列の先頭に属する値が見つかったら、次に配列の2番目の位置に属する値を探してみよう。

After we've done that, we'll try and find the value that belongs in the third position of the array.

それが終わったら、配列の3番目の位置に属する値を探してみよう。

So let's go back and talk about that first step.

では、最初のステップに戻って話をしよう。

We want to know what belongs in the first position of the array.

配列の最初の位置に属するものを知りたい。

これらは選別されることを忘れないでほしい。

The thing that belongs in the very first position will end up being the smallest number overall, the minimum value.

最初の位置に属するものは、結局、全体として最小の数、最小値となる。

So let's think about the steps that a computer program is going to have to go through in order to find the minimum value.

そこで、コンピュータ・プログラムが最小値を求めるために踏むステップについて考えてみよう。

Now, when we see this visually, our brain is so good that it just instantly looks at the values and identifies the first one.

さて、これを視覚的に見たとき、私たちの脳は非常に優れているので、瞬時に値を見て最初の値を特定する。

But remember that a computer program isn't visual.

しかし、コンピュータープログラムは視覚的なものではないことを忘れないでほしい。

It's looking at an individual box and then somehow comparing it and contrasting it with others.

個々の箱を見て、それをどうにかして他の箱と比較対照するんだ。

So when our program first looks at this box, it has nothing to compare it to.

つまり、私たちのプログラムが最初にこの箱を見たとき、比較するものが何もないのだ。

そして2はかなり良い選択だと思う。

That might be the thing that belongs in the beginning of this array.

それはこの配列の最初に属するものかもしれない。

So I'm going to use my pencil here to keep track of which item I'm evaluating.

だから、ここで鉛筆を使って、どの項目を評価しているかを記録しておこうと思う。

And I'm going to indicate the one that seems like my candidate for the best possible value by slightly offsetting it.

そして、可能な限り最良の値の候補と思われるものを、少し相殺する形で示すつもりだ。

So when we get to 34, that's no better than 2.

だから、34歳になっても2歳以下だ。

だから、1をブックマークしておこうと思う。

And I'm going to continue on, even though we know visually that 1 is our best value.

そして、1がベストバリューだと視覚的に分かっていても、私は続けるつもりだ。

Remember, the computer is processing step by step.

コンピューターはステップ・バイ・ステップで処理していることを忘れないでほしい。

There could be a negative number out here or a 0.

ここにはマイナスの数字があるかもしれないし、0かもしれない。

So I get to 3, no better than 1. 89, no better than 1. 13, no better than 1. 55, no better than 1.

1.89以下、1.13以下、1.55以下、1.1以下。

So I've gone all the way through my data and I've found the minimum value overall.

だから、自分のデータを全部調べて、総合的に最小値を見つけたんだ。

And I know that that belongs in the very first position of my array.

そして、それが私の配列の一番最初の位置にあることも知っている。

だから、この2つを入れ替えようと思う。

Not only that, I'm going to kind of set this off to the side and kind of ignore it.

それだけでなく、私はこれを横に置いて、無視するつもりだ。

I know that that belongs in the very first position of my array.

それが私の配列の一番最初の位置にあることは分かっている。

Oh, at this point, I can repeat the process starting from the second position.

ああ、この時点で、2番目のポジションからプロセスを繰り返すことができる。

So I've already removed the overall minimum value and kind of set it off to the side.

だから、全体的な最小値はすでに削除して、横に置いてあるんだ。

Now if I process the remainder of my array in the exact same way and find the minimum value of what's remaining, that's going to be my second minimum value and belong in the second position of the array.

さて、配列の残りをまったく同じように処理して、残ったものの最小値を求めると、それが2番目の最小値となり、配列の2番目の位置に属することになる。

So let's go through this exercise a few more times. 34 seems pretty good when I first look at it, but then I move on to 2 and that's much better. 3 is no better than 2. 89 is no better than 2. 13 is no better than 2. 55 is no better than 2.

では、この練習をもう少し繰り返してみよう。34は最初に見たときはかなり良いように思えたが、次に2に進むと、2の方がずっと良い。3は2より良くない。89は2より良くない。13は2より良くない。55は2より良くない。

So we get to the end and now we know that 2 belongs in that second position.

これで、2が2番目のポジションに属することがわかった。

And again, I'm leaving a little gap here so I can kind of tell where my unsorted data begins and where my sorted data is at.

また、ソートされていないデータがどこから始まって、ソートされたデータがどこにあるのかがわかるように、ここでは少し隙間を空けている。

Now I'm at the third position of the array.

今、私は配列の3番目の位置にいる。

I've removed the minimum overall and the second minimum.

全体の最低ラインと2番目の最低ラインは削除した。

So let's go through the process again. 34 seems pretty good until I see 3. 89, 13, and 55.

では、もう一度確認しよう。3、89、13、55を見るまでは、34はかなり良いように思える。

Now I've got fully sorted data for 3 items and then I've got my unsorted set.

これで、3つのアイテムについて完全にソートされたデータが揃った。

That's okay. 89, oh, 13 is better than my 34. 55 is no better.

大丈夫だよ。89、ああ、13は僕の34よりいい。55の方が全然いい。

Swap my minimum value with my first value.

最小値と最初の値を入れ替える。

Repeat the process. 89 seems pretty good until I happen to stumble across the 34. 55 is no better than 34.

それを繰り返す。たまたま34に出くわすまでは、89はかなりいいように思える。55は34より良くない。

I have my sorted set and my unsorted set. 89 seems pretty good until I see 55.

私はソートされたセットとソートされていないセットを持っている。55を見るまでは、89はかなりいいと思う。

そして今、私のソートセットには55がある。

My unsorted set only has one number so we'll just go ahead and add that on.

私のソートされていないセットには数字が1つしかないので、それを追加することにしよう。

At this point I'm done and it's completely sorted.

この時点で、私は仕事を終え、完全に解決した。

So remember that I was doing the bulk of the work in this process of selecting the next item, which is why this is called selection sort.

だから選択ソートと呼ばれているのだ。

Okay, of course, this process isn't limited to just numbers.

もちろん、このプロセスは数字だけに限ったことではない。

We could also use this idea of selection sort with words or anything else that we can construct a total ordering out of.

また、この選択ソートという考え方を、単語やその他のもので、全体的な順序を構成できるものにも使うことができる。

So these are the surnames of some relatively famous computer scientists.

以上が、比較的有名なコンピューター科学者の苗字である。

So starting with Hopper seems like a good candidate for a first overall.

だから、ホッパーから始めるのが全体1位候補としては良さそうだ。

Turing's no earlier in the alphabet than Hopper.

チューリングはホッパーよりアルファベットの方が早いんだ。

Then we get to Corman, and Corman doesn't come any earlier than Allen, so Allen goes to the front.

そしてコーマンに行き、コーマンはアレンより早く来ないので、アレンが前に行く。

Hopper gets swapped back to where Allen was just at.

ホッパーは入れ替わりでアレンがいた場所に戻る。

このプロセスを何度も繰り返す。

Turing seems pretty good until we see Rivest.

チューリングは、リベストを見るまではかなり良いように思える。

そして、ホッパーはさらに良くなったようだ。

そしてコーマンはさらに素晴らしい。

 Okay, anyway, so the basic idea is that we can even do this sorting process with other types of data, not just with integers, so it does generalize.

とにかく、基本的な考え方は、整数だけでなく、他のデータ型でもこのソート処理を行うことができるということだ。