整列

プログラミング言語のいくつかの基準に基づいて、配列などの順序を持つ資料型要素をソートする関数があります.Javascript標準にはsortという良い関数があります.しかし、自分が望む基準に沿って並べる場合は、想像以上に多くなりがちです.最近、ある数字でソートするのではなく、その数字に基づいて文字をソートする問題が発生しました.これはsort関数を配列に適用する問題ではない.したがって,順序付けの論理を考えると有用である.もっと良い方法がたくさんありますが、私はまず私の考えている論理を実現しました.

1.最初の要素を保持

比較可能なオブジェクトがないため、最初の要素は保持されます.

2.比較する要素の抽出

位置が変化しなくても、後で元の位置に挿入できるので、要素を抽出します.この要素をtemporal value(一時値、以下tempValと略す)と呼びます.

3.ナビゲーション挿入位置

抽出した位置より前の位置を検索します.抽出された位置より前の値が順番に並べ替えられているため、以前の位置値から抽出された値がどのインデックスにあるかを決定すると、並べ替えは終了します.抽出値が前の場所に存在する値より小さい場合は、インデックス値を小さくし続け、前の値にtempValより大きい値があるかどうかを確認します.ナビゲーション終了条件は、tempVal値が位置より大きい値、またはインデックス値が0です.どちらの場合も、抽出されたtempValは特定の位置に配置されます.

4.ナビゲーション位置に要素を挿入する

インデックス値を0番目のインデックス値より小さくすると、当然、0番目のインデックス位置に値が挿入されます.tempVal値が位置の値より大きい場合は、その特定の位置+1のインデックスにtempVal値を挿入します.

例

文字で整理すると、頭の中で考えているよりも簡単に見えます.例えば、単純な配列[5,2,8,1]が適用される.

1.最初の要素を保持

最初の要素(0をインデックス、以下をインデックス)5を保持します.

2.比較する要素~3を抽出します。ナビゲーション挿入位置

最初のインデックス値2を抽出します.抽出後の配列は[5,8,1]となる.最初のインデックスなので、以前のインデックスは0しかありませんでした.0番目のインデックス要素は5で、抽出された要素2は5未満です.したがって、インデックスを減らす必要がありますが、0は最小のインデックスなので、抽出された要素を0番目の場所に挿入します.

最終的な配列は[2,5,8,1]であった.

2番目のインデックス値8を抽出します.抽出後の配列は[2,5,1]となる.2番目のインデックスなので、前のインデックス1からナビゲートします.8は1番目のインデックスの値5より大きいので、インデックスを減らす必要はなく、位置+1の2番目のインデックスに挿入するだけです.

最終的には[2,5,8,1]に配列され,結果は抽出された元の位置に位置した.

3番目のインデックス1を抽出します.抽出後の配列は[2,5,8]であった.3番目のインデックスなので、前のインデックス2からナビゲートを開始します.2番目のインデックス値は8で、1は8未満です.したがって、インデックスを1に減らします.

最初のインデックス値は5で、1は5未満です.したがって、インデックスをゼロに減らします.

0番目のインデックス値は2ですか、1が2未満ですか.したがって、インデックスを減らす必要がありますが、ナビゲーションインデックスは0なので、減らす必要はありません.0番目のインデックスに値を挿入します.

最終的な配列は［1,2,5,8］であった.

インプリメンテーション

これに基づいてJavascriptを用いてコード化する.

const originArr = [5, 2, 8, 1];
let tempArr = [];
let tempVal;
for(let i = 0; i<originArr.length; i++){
  tempArr.push(originArr[i]);
  if(i>0){
    tempVal = tempArr.pop() // 
    let k = i;
    while(true){
      // searching condition (decreasing index)
      if(tempVal < tempArr[k-1]){
        k--;
      }
      // insert & escape condition
      else if (tempVal >= tempArr[k-1] || k === 0){
        tempArr.splice(k, 0, tempVal);
        break;
      }
    }     
  }
}
console.log(`original array : [${originArr}]`)
console.log(`sorted array : [${tempArr}]`) // expect to [1, 2, 5, 8]

字を吟味するよりもコード化するのは容易ではないが、頭の中で考えるよりは容易ではない.論理を考えておくと役に立つかもしれないので、まず整理しておきます.