元記事
バブルソートアルゴリズム - DEV Community
Maximilian
はじめに
私は最近、低レベルプログラミングとコンピュータサイエンスの概念を学ぶ一環として、データ構造とアルゴリズムのコースを受講しました。ことわざにもあるように、何かを教えることが知識を定着させる最良の方法です。そして、今月（おそらく今年）はコーディングの話でパートナーを退屈させる分のノルマをすでに果たしてしまったので、学んだことの一部を投稿シリーズにしようと思いました。これはそのような投稿の1つです。
バブルソートアルゴリズムとは
バブルソートアルゴリズムは、効率よりも単純さが好まれる場面で通常用いられます。時間計算量はO(n^2)で、より大きなリストを扱う場合には理想的とは言えません。
どのように動作するのか
動作を説明するために、疑似コードを示します：
for pointer1 in list
for pointer2 in list
if list[j] > list[j + 1]
swap list[j] and list[j + 1]
pointer2++
pointer1++
このアルゴリズムの考え方は、リスト内のより大きな項目を末尾へ「バブルアップ」させることです。これは2つのポインタ、pointer1とpointer2で考えることができます。まず、両方のポインタをリストの最初の項目に設定します。次に、pointer2でリスト全体を進みながら、pointer2 + 1の位置の項目の値が大きい場合、pointer2の位置の項目を交換します。これをリストの末尾に到達するまで繰り返します。その後、pointer1を1つ進め、pointer2で同じ処理を再び開始します。
すでにソート済みの項目をチェックしないようにする方法が必要だと気づいたかもしれません。各反復の目的はより大きな項目をリストの末尾へ移動させることなので、pointer2の境界をpointer1 + 1の値で制限することで実現できます。
どのように実装するのか
以下は、コメントを多く付けたTypescriptでの実装です：
function bubbleSort(arr: number[]): void {
// pointer 1
for (let i = 0; i < arr.length; ++i) {
// pointer 2 + limit iterations by pointer1 + 1
for (let j = 0; j < arr.length - 1 - i; ++j) {
// check if current item is larger than the next item
if (arr[j] > arr[j + 1]) {
// temporarily store the current item so we don't lose it
const tmp = arr[j];
// swap the items in the array
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
ソート完了
これは多くの場合に最初に選ぶようなアルゴリズムではありませんが、始めるにはシンプルで簡単なものだと思います。役に立った、あるいは少なくとも少しでも面白いと感じてもらえたなら幸いです！