アルゴリズム03ソートデフォルト|選択ソート、バブルソート、挿入ソート|JS

ソートアルゴリズムのタイプ

simple, slowfastO(N)Selection sort, Bubble sort, Insertion sortQuicksort, Merge sort,Heap sortradix sort

ソート選択|Sortの選択

の最大値を見つけて、最後の位置を置き換えます.

時間複雑度:O(n^2)

// 오름차순, 최소값을 맨 앞자리와 바꾸는 방식
function selectionSort(arr) {
  const len = arr.length
  let minIndex = 0
  let temp = 0
  let i = 0
  let j = 0
  for (i = 0; i < len; i++) {
    minIndex = i
    for (j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        minIndex = j
      }
    }
    temp = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = temp
  }
  return arr
}

const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(selectionSort(arr))

バブル整列|Bubble Sort

画像ソース
2つの隣接する要素をチェックしてソートする方法

元素の移動が泡状に水面に浮かぶことから

と名付けられた.

時間複雑度:O(n^2)

// 오름차순
function bubbleSort(arr) {
  const len = arr.length
  let temp = 0
  let i = 0
  let j = 0
  for (i = 0; i < len; i++) {
    for (j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}


const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(bubbleSort(arr))

挿入位置合わせ|挿入Sort

リソースアレイ内のすべての要素を、前の順序で配列するアレイ部分と比較し、それらの位置を検索して挿入することによって

に並べ替える.

時間複雑度:O(n^2)

[挿入位置合わせ](Insert Align)(ドアの冗長性)

function insertionSort(arr) {
  const len = arr.length
  let temp = 0
  for (i = 1; i < len; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[i] < arr[j]) {
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
        i--
      }
    }
  }
  return arr
}

const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(insertionSort(arr))

挿入位置合わせ(文+while文用)

リファレンス

function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    index = i;
    while (arr[index] !== undefined && arr[index - 1] > arr[index]) {
      let temp = arr[index - 1];
      arr[index - 1] = arr[index];
      arr[index] = temp;
      index--;
    }
  }
}

📚 リファレンス

YOUTUBE|2015春学期アルゴリズム|権五鑫
Photo by Michael Dziedzic on Unsplash