[Topic #자료구조 06] 기본 정렬 3가지(선택/버블/삽입) 구현 with JavaScript

// Ascending Order Sort

// 선택 정렬
// T.C: O(n^2)
// S.C: O(n) - B/C make it to a pure function
const selectionSort = (array) => {
  const len = array.length;
  const copyArr = [...array]; // array.slice() - 얕은 복사
  for (let i = 0; i < len; i += 1) {
    let minIdx = i;
    for (let j = i + 1; j < len; j += 1) {
      if (copyArr[minIdx] > copyArr[j]) {
        minIdx = j;
      }
    }
    [copyArr[i], copyArr[minIdx]] = [copyArr[minIdx], copyArr[i]];
  }
  return copyArr;
};

// 버블 정렬
// T.C: O(n^2)
// S.C: O(n) - B/C make it to a pure function
const bubbleSort = (array) => {
  const len = array.length;
  const copyArr = [...array];
  for (let i = len - 1; i >= 1; i -= 1) {
    for (let j = 0; j < i; j += 1) {
      if (copyArr[j] > copyArr[j + 1]) {
        [copyArr[j], copyArr[j + 1]] = [copyArr[j + 1], copyArr[j]];
      }
    }
  }
  return copyArr;
};

// 삽입 정렬
// T.C: O(n^2), Best Case[pre-sorted] - O(n)
// S.C: O(n) - B/C make it to a pure function
const insertionSort = (array) => {
  const len = array.length;
  const newArray = [array[0]];
  for (let i = 1; i < len; i += 1) {
    const value = array[i];
    let j = newArray.length - 1;
    while (j >= 0 && newArray[j] > value) {
      newArray[j + 1] = newArray[j];
      j -= 1;
    }
    newArray[j + 1] = value;
  }
  return newArray;
};

// Simple Test cases
const arr1 = [4, 1, 5, 9, 3, 2, 7, 8, 6];
console.log(selectionSort(arr1));
console.log(bubbleSort(arr1));
console.log(insertionSort(arr1));

---

자세한 내용은 추후 업데이트 하겠습니다