Toy_ #13. insertionSort

整列挿入

整列挿入

一度に1つの項目の配列を記入します.

1回転を行うたびにインデックスが増加し、そのインデックスへの要素のソートが終了します.

時間の複雑さ

最適:O(N)

最悪:O(N^2)

平均:O(N^2)

長所

は安定したソートアルゴリズムである.

アレイは、ほとんどの場合ソートされ、非常に効率的です.

短所

配列の要素移動数が多い.

アレイのサイズが大きい場合は、時間がかかります.

注：yujoのベル

質問する

要素の整数の配列を入力し、昇順に並べ替えて返します.

に注意

挿入ソートを実装する必要があります.

arr.sortの使用を禁止します.

(Advanced)insertionSort関数の2番目のパラメータとしてコールバック関数を受け入れ、その関数の戻り値に基づいて要素をソートします.

に答える

const insertionSort = function (arr, transform = (item) => item) {

  // 두 번째 인덱스 수부터 바로 앞 인덱스의 값과 비교하여 정렬한다.

  let aux = [arr[0]];
  // 비교할 첫 번째 요소는 따로 선언해 놓는다.

  for(let i = 1; i < arr.length; i++) {
    if (transform(arr[i]) >= transform(aux[i - 1])) {
      // 현재 요소 값이 비교할 앞 인덱스의 요소보다 크면, 현재 요소 값을 따로 선언한 배열에 push한다.
      aux.push(arr[i])
    }
    else {
      for (let j = 0; j < i; j++) {
        // 그렇지 않은 경우 aux의 배열의 길이만큼 (i의 숫자 크기만큼) for문을 돌려
        if (transform(arr[i]) <= transform(aux[j])) {
          // aux의 전체 요소값 중에 현재 요소 값보다 큰 값이 있는 경우
          const left = aux.slice(0, j);
          // 해당 현재 요소 값을 해당 큰 값 바로 앞에 끼워 넣어야 한다.
          // 큰 값 바로 앞 left
          const right = aux.slice(j);
          // 큰 값 바로 뒤 right로 선언하고
          aux = left.concat(arr[i], right)
          // 사이에 현재 요소 값을 넣어 준다.
          break;
          // swap한 후 else 반복문을 멈춘다.
        }
      }
    }
  }
  return aux
};

ソートの挿入、要素値の比較、swapの比較を学習することで問題を解くことを試みたが、高度な問題の効果は芳しくなかった.最後に文献を参考にした.

参照コードは、パラメータとしての配列の要素の位置を変更するのではなく、aux配列を単独で作成し、パラメータとしての配列の最初の要素を入れ、実際のパラメータ配列では2番目の要素から確認します.

コールバック関数transform = (item) => itemに関数を入れることはまだ正確には理解できませんが、現在のコールバック関数では、コールバック関数が外部でパラメータを指定していない場合、関数内部の式は依然として正しいです.また外で指定すると,そのコールバックは内部意識の回帰と理解できる.