정렬 알고리즘 (버블, 선택, 삽입, 병합, 퀵)

버블 정렬 (bubble sort)

• 버블정렬은 두 인접한 원소를 검사하여 정렬하는 방법
• 시간 복잡도는 느리지만 코드가 단순하다
• 배열 전체를 순회하며 비교하기 때문에 시간복잡도는 O(n²)
• 배열 하나만 사용하기 때문에 공간복잡도는 O(n)

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

const arr = [4, 3, 8, 5, 2, 1];
console.log(bubbleSort(arr)); // [1, 2, 3, 4, 5, 8]

선택 정렬 (selection sort)

• 배열의 가장 작은 값을 가지는 인덱스를 찾아서 가장 작은 값을 앞에서부터 채워나가면서 정렬하는 방식.
• for loop 2번을 통해 배열을 훑고, swap하는 방식으로 시간복잡도는 O(n²)
• 공간복잡도는 O(n)

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

const arr = [99, 3, 7, 9, 5, 10, 25, 17];
console.log(selectionSort(arr)); // [3, 5, 7, 9, 10, 17, 25, 99]

삽입 정렬 (insertion sort)

• 최소값을 찾아서 이하 배열들의 원소와 비교하여 자신이 위치해야할 곳을 찾아 삽입해나가며 정렬하는 방식이다.
• for loop 혹은 while loop를 2중첩으로 구현되어 시간복잡도는 O(n²)
• 공간복잡도는 O(n)

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let cur = arr[i];
    let left = i - 1;

    while(left >= 0 && arr[left] > cur) {
      arr[left + 1] = arr[left];
      left--;
    }
    arr[left + 1] = cur;
  }
  return arr;
}

const arr = [5, 3, 7, 39, 28, 6, 1];
console.log(insertionSort(arr)); // [1, 3, 5, 6, 7, 28, 39]

병합 정렬 (merge sort)

• 배열을 반씩 쪼개서 하나의 원소를 가진 배열로 만든 후 비교를 통해 각 배열을 정렬하여 병합하여 최종 정렬된 배열을 구하는 정렬방식이다.
• 배열을 반씩 쪼개며 정렬을 하고 다시 그것을 병합하는 방법으로 시간복잡도는 O(nlogn)
• 공간복잡도는 O(n)

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

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

function merge(left, right) {
  const result = [];
  
  while(left.length && right.length) {
    if(left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while(left.length) {
    result.push(left.shift());
  }
  while(right.length) {
    result.push(right.shift());
  }

  return result;
}

const arr = [3, 5, 2, 8, 9, 1, 9, 39, 28];
console.log(mergeSort(arr)); // [1, 2, 3, 5, 8, 9, 9, 28, 39]

퀵 정렬 (quick sort)

• 기준이 되는 기준점을 가지고 앞/뒤 배열로 쪼개서 각 앞/뒤배열을 기준값 보다 작은수를 앞으로 몰고 기준값보다 큰 수를 재귀함수를 통해 뒤로 몰아가는 정렬방식
• 배열을 기준점으로 나누어 해당 기준값을 기준으로 좌,우의 배열을 다시한번 탐색하며 정렬하는 방식으로 시간복잡도는 O(nlogn)
• 공간복잡도는 O(n)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[0];
  const left = [];
  const right = [];

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

  return quickSort(left).concat(pivot, quickSort(right));
}

const arr = [4, 8, 2, 1, 3, 5, 9];
console.log(quickSort(arr)); // [1, 2, 3, 4, 5, 8, 9]

References

정렬 알고리즘 정리(With Big O Notation)
[알고리즘] 퀵 정렬(quick sort)이란
Big-O Notation Explained