[JavaScript] 1. 정렬 알고리즘

1. 선택 정렬

선택 정렬은 배열에서 최소값을 찾아 맨 앞의 원소와 교환하는 방식입니다.

function selectSort(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;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

const array2 = [25, 20, 10, 30, 50];
console.log("sort:", selectSort(array2)); // sort: [ 10, 20, 25, 30, 50 ]

---

2. 삽입 정렬

삽입 정렬은 정렬된 부분과 정렬되지 않은 부분을 나누어, 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입하는 방식입니다.

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const 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;
}

const array3 = [12, 11, 13, 5, 6];
console.log("삽입 정렬:", insertionSort(array3));

---

3.병합 정렬

병합 정렬은 분할 정복 알고리즘으로, 배열을 반으로 나누고 정렬한 후 병합하는 방식입니다.

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]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

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

const array4 = [38, 27, 43, 3, 9, 82, 10];
console.log("병합 정렬:", mergeSort(array4));

---

4. 퀵 정렬

퀵 정렬은 피벗을 기준으로 배열을 나누고, 재귀적으로 정렬하는 방식입니다.

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 array4 = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = quickSort(array4);
console.log("퀵 정렬:", sortedArray); // [3, 9, 10, 27, 38, 43, 82]

---

 

GitHub - Koras02/javascript-algorithm