코딩테스트 정렬

// 정렬 알고리즘 구현 예제

/**
 * 1. 거품 정렬 (Bubble Sort)
 * @param {number[]} arr - 정렬할 배열
 * @returns {number[]} - 정렬된 배열
 */
function bubbleSort(arr) {
  const n = arr.length
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // swap
      }
    }
  }
  return arr
}

/**
 * 2. 선택 정렬 (Selection Sort)
 * @param {number[]} arr - 정렬할 배열
 * @returns {number[]} - 정렬된 배열
 */
function selectionSort(arr) {
  const n = arr.length
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] // swap
    }
  }
  return arr
}

/**
 * 3. 삽입 정렬 (Insertion Sort)
 * @param {number[]} arr - 정렬할 배열
 * @returns {number[]} - 정렬된 배열
 */
function insertionSort(arr) {
  const n = arr.length
  for (let i = 1; i < n; i++) {
    let key = arr[i]
    let j = i - 1
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = key
  }
  return arr
}

/**
 * 4. 병합 정렬 (Merge Sort)
 * @param {number[]} arr - 정렬할 배열
 * @returns {number[]} - 정렬된 배열
 */
function mergeSort(arr) {
  if (arr.length <= 1) return arr

  const mid = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))

  return merge(left, right)
}

// 병합 함수
function merge(left, right) {
  const result = []
  let i = 0,
    j = 0

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++])
    } else {
      result.push(right[j++])
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j))
}

/**
 * 5. 퀵 정렬 (Quick Sort)
 * @param {number[]} arr - 정렬할 배열
 * @returns {number[]} - 정렬된 배열
 */
function quickSort(arr) {
  if (arr.length <= 1) return arr

  const pivot = arr[arr.length - 1]
  const left = []
  const right = []

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)]
}

// 테스트 데이터
const arr = [64, 25, 12, 22, 11]

// 정렬 알고리즘 실행
console.log('거품 정렬:', bubbleSort([...arr]))
console.log('선택 정렬:', selectionSort([...arr]))
console.log('삽입 정렬:', insertionSort([...arr]))
console.log('병합 정렬:', mergeSort([...arr]))
console.log('퀵 정렬:', quickSort([...arr]))