우크라이나어 하는 개발자

버블 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const swap = (arr, index, nextIndex) => {
  [arr[index], arr[nextIndex]] = [arr[nextIndex], arr[index]]
}

const bubbleSort = (arr) => {
  for (let i = arr.length; i >= 0; i--) {
    let noSwap = true
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        noSwap = false
      }
    }
    if (noSwap) break
  }
  return arr
}

선택 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const swap = (arr, index, nextIndex) => {
  [arr[index], arr[nextIndex]] = [arr[nextIndex], arr[index]]
}

const selectionSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      swap(arr, i, lowest)
    }
  }
  return arr
}

삽입 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    console.log(arr)
    let currentValue = arr[i]
    for (let j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
      arr[j + 1] = arr[j]
      arr[j] = currentValue
    }
  }
  return arr
}