泡の位置合わせ

4062 ワード
algorithm テキストリンク

サマリ


2つの隣接する要素のサイズを比較し、条件に合致しない場合は、アルゴリズムを交換してソートします.

プロセス



時間の複雑さ

  • 最適例:O(n)-改良された泡配列
  • Worst Case: O(n^2)

    • くうかんふくざつさ

  • は、所与の配列において交換順序付けされるので、O(1)である.

    • 長所

  • の実装は非常に簡単です.
  • アレイでスワップするため、他のメモリ領域のその場ソートは必要ありません.
  • 安定したソート.

    • 短所

  • はあまり効率的ではありません.
  • 交換演算がたくさんあります.

    • コード実装

    // 개선된 Bubble Sort
const bubbleSort = (arr) => {
  let noSwap;
  for (let i = arr.length; i > 0; i--) {
    noSwap = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwap = false;
      }
    }
    if (noSwap) break;
  }
  return arr;
};
    JDK ArrayListソースコード解析
    超軽量タイマー