元記事
バブルソートアルゴリズム - 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;
}
}
}
}
まとめ
これは多くの場合、最初に選ぶようなアルゴリズムではありませんが、始めるにはシンプルで簡単なものだと思います。お役に立てたなら、あるいは少なくとも少しでも興味深いと思っていただけたら幸いです!