泡の位置合わせ

2つの隣接するデータ値を比較しながら、交換位置で並べ替えます.
複数の要素のみをソートする狭い範囲に集中します.
n個の要素をBubbleソートするたびに、n個目の要素がソートされます.
例えば、5、1、6、2、4、3を昇順に並べ替えるとする.
まず5、1を比較して、1は5より小さいので、位置を変えます.
次の5,6を比較すると、正しい順番なのでスキップします.
すべての要素が整列するまで、上記の手順を繰り返します.

時間の複雑さ

worst case : O(n^2)

未ソート時

best case : O(n)

ソート済

インプリメンテーションアルゴリズム

function bubbleSort(arr) {
  for(let i=0; i<arr.length; i++) {
    let swap;
    for(let j=0; j<arr.length-1-i; j++) {
      if(arr[j] > arr[j+1]) {
        swap = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = swap
      }
    }
    
    if(!swap) break
  }
  return arr
}

ソートの選択

配列中の資料の最小数(または最大数)を見つけ、最初の位置(または最後の位置)の数を交換するようにソートします.
交換回数は最も少なく,各資料を比較する回数は増加した.
Bubbleソートの例に示すように、5、1、6、2、4、および3をソートする場合.
0番目のインデックス値5で開始します.
5を[1,6,2,4,3]と比較して最適値を求めた.
1(最小)と5の位置を入れ替えます.
1以外の5、6、2、4、3の中で最高値を探します.
2(最小の数)と5の位置が入れ替わる.

時間の複雑さ

worst case : O(n^2)

未ソート時

best case : O(n^2)

ソート済

毎回指定された位置に到達できる最高値を見つけるのでn^2となります.非常に非効率なソート

インプリメンテーションアルゴリズム

function selectionSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      let swap = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = swap;
    }
    console.log(`${i}회전: ${array}`);
} 
  return arr;
}

整列挿入

ソートされていない部分の資料がソート部分の位置に挿入される形式のソート方法.
5、1、6、2、4、3を挿入ソートにソートすると、
配列の最初の位置が整列された部分であると仮定します.
5以外の1、6、2、4、3はいずれも並べ替えられていない部分であり、そのうち1番目の位置の1は5未満であるため、1を5の前に置く.
ソートされていない部分6、2、4、3のうち6は5より大きいのでスキップします.
2、4、3～2を並べ替えた1、5、6と比較し、1、5の間に置きます.

時間の複雑さ

worst case : O(n^2)

未ソート時

best case : O(n)

ソート済

インプリメンテーションアルゴリズム

function insertionSort (array) {
  //정렬할 배열을 순회한다.
  for (let i = 1; i < array.length; i++) {
    //현재 비교할 순자를 뽑는다.
    let cur = array[i];
    //왼쪽 부분(정렬된 부분)
    let left = i - 1;
    //왼쪽 부분 숫자들과 현재 숫자를 계속 비교
    while (left >= 0 && array[left] > cur) {
      array[left + 1] = array[left];
      array[left] = cur;
      cur = array[left];
      left--;
    }
  }
  return array;
}

連結ソート

これは、要素が1つになるまで半連続で並べ替えられます.
3 5 2 6 4 1を半分に分ける
[3.5.2][6.4.1]各配列を再び二つに分ける
エレメントが分割されるまで、エレメントをソートしてマージします.

時間の複雑さ

O(nlogN)

インプリメンテーションアルゴリズム

function mergeSort (array) {
  if (array.length < 2) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);
  
  return merge(mergeSort(left), mergeSort(right));
  
  //병합을 위한 함수
  function merge (left, right) {
    const resultArray = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
      } else {
        resultArray.push(right[rightIndex]);
        rightIndex++;
      }
    }
    return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
  }
}

コードソース:[コードPlayground]