[JavaScript] 기본

자바스크립트 공부에 용이하도록 기본적인 정렬 알고리즘을 모아봤다.

---

버블 정렬

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

• 인접한 두 원소를 비교하여 큰 값을 뒤로 보내며 정렬하는 알고리즘입니다.
• 한 번의 반복에서 가장 큰 값을 마지막 위치에 보내는 것이 보장되므로, 다음 반복에서는 마지막 위치를 제외하고 이를 반복하며 정렬합니다.
• 구현이 간단하지만, 비효율적인 알고리즘이며, 시간 복잡도는 언제나 O(n^2)입니다.

---

삽입 정렬

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

• 현재 위치에서 그 이하(왼쪽)의 배열들을 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘입니다.
• 삽입할 위치를 찾는 데에 대해 비교적 적은 비교 연산이 필요하기 때문에, 배열이 거의 정렬된 상태일 때 효율적입니다.
• 최악의 경우 시간 복잡도는 O(n^2)이지만, 대부분의 경우 거의 정렬된 상태일 때 효율적으로 동작하여 O(n)의 시간 복잡도를 가집니다.

---

선택 정렬

function selectionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    let min = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    if (i !== min) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
  return arr;
}

• 가장 작은(혹은 가장 큰) 값을 찾아서 첫 번째 위치(혹은 마지막 위치)와 교환하고, 다음으로 작은(혹은 큰) 값을 찾아 두 번째 위치(혹은 마지막에서 두 번째 위치)와 교환하고, 이를 반복적으로 수행하는 정렬 알고리즘입니다.
• 구현이 간단하지만, 비효율적인 알고리즘이며, 시간 복잡도는 언제나 O(n^2)입니다.

---

퀵 정렬

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  let pivot = arr[right];
  let pivotIndex = left;
  for (let i = left; i < right; i++) {
    if (arr[i] < pivot) {
      let temp = arr[i];
      arr[i] = arr[pivotIndex];
      arr[pivotIndex] = temp;
      pivotIndex++;
    }
  }
  let temp = arr[right];
  arr[right] = arr[pivotIndex];
  arr[pivotIndex] = temp;
  return pivotIndex;
}

• 분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 수행 속도를 가지는 정렬 알고리즘입니다.
• 피벗(pivot)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하고, 분할된 두 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다.
• 최악의 경우(피벗이 항상 최소값 또는 최대값인 경우 등) 시간 복잡도가 O(n^2)이지만, 평균적으로 O(nlogn)의 시간 복잡도를 가집니다.

---

합병정렬

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);
  
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr);
  
  return merge(sortedLeftArr, sortedRightArr);
}

function merge(leftArr, rightArr) {
  const resultArr = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      resultArr.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      resultArr.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }
  
  return resultArr.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}

위 코드는 mergeSort 함수와 merge 함수로 이루어져 있습니다. mergeSort 함수는 배열을 반씩 나누어 재귀적으로 호출하며, 배열의 길이가 1 이하가 될 때까지 반복합니다. 그리고 마지막으로 merge 함수를 호출하여 왼쪽 배열과 오른쪽 배열을 병합합니다.

merge 함수는 왼쪽 배열과 오른쪽 배열을 인수로 받아 두 배열을 병합합니다. 병합하는 과정에서 왼쪽 배열의 첫번째 요소와 오른쪽 배열의 첫번째 요소를 비교하여 작은 값을 결과 배열에 추가하고, 해당 배열의 인덱스를 증가시킵니다. 그리고 왼쪽 배열이나 오른쪽 배열 중 하나가 모두 결과 배열에 추가될 때까지 위 과정을 반복합니다. 마지막으로 왼쪽 배열과 오른쪽 배열 중 하나가 이미 모두 결과 배열에 추가되었다면, 남은 요소들을 결과 배열 뒤에 추가하여 정렬을 완료합니다.

위 코드를 실행하면 주어진 배열이 합병 정렬을 통해 정렬된 결과를 반환합니다.

---

let, const, var 차이점

let, const, var는 모두 변수를 선언하기 위한 키워드입니다. 하지만 선언 방식과 변수의 특징이 각각 다르기 때문에 이들을 혼동하면 문제가 발생할 수 있습니다.

var

• ES6 이전에 사용되던 변수 선언 키워드입니다.
• 함수 스코프를 갖습니다. 즉, 함수 내에서 선언된 변수는 함수 내에서만 접근 가능합니다.
• 변수를 선언하기 전에 참조할 수 있습니다. 이를 호이스팅(hoisting)이라고 합니다.
• 변수를 중복 선언해도 오류가 발생하지 않습니다.

let

• ES6에서 추가된 블록 스코프를 갖는 변수 선언 키워드입니다.
• 중복 선언이 불가능합니다. 같은 이름의 변수를 다시 선언하면 오류가 발생합니다.
• 호이스팅이 발생하지 않습니다. 변수를 선언하기 전에 참조하면 오류가 발생합니다.
• 블록({}) 내에서 선언된 변수는 블록 내에서만 접근 가능합니다.

const

• let과 마찬가지로 ES6에서 추가된 블록 스코프를 갖는 변수 선언 키워드입니다.
• let과 달리 상수(constant)를 선언할 때 사용합니다. 한 번 선언된 값은 변경할 수 없습니다.
• 중복 선언이 불가능합니다. 같은 이름의 변수를 다시 선언하면 오류가 발생합니다.
• 호이스팅이 발생하지 않습니다. 변수를 선언하기 전에 참조하면 오류가 발생합니다.
• 블록({}) 내에서 선언된 변수는 블록 내에서만 접근 가능합니다.
• 따라서 변수를 선언할 때는 변수의 스코프, 값의 변경 가능 여부 등을 고려하여 적절한 키워드를 선택해야 합니다. 일반적으로는 let과 const를 사용하는 것을 권장합니다. var는 호이스팅 등으로 인해 예상치 못한 오류가 발생할 가능성이 있기 때문입니다.