[Algorithm] Sort

코딩을 하다보면 데이터를 정렬할 필요가 있는데 정렬 하는 방법도 다양하기에 상황에 따라 적합한 정렬법을 적용해야 정렬한 데이터를 활용 할 때의 시간도 줄어든다.

정렬하는 방법은 다양하지만 이 게시글에서는 다음의 7가지의 정렬 알고리즘을 가볍게 훑고 지날 갈것이다.

7가지 정렬 알고리즘

• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 퀵 정렬
• 병합 정렬
• 힙 정렬
• 계수 정렬

---

✍ 선택 정렬 (Selection Sort)

선택 정렬의 경우 가장 흔한 정렬 중 하나로, 목록에서 최소 요소를 찾아 첫 번째 요소로 교체하는 것으로 시작하는 알고리즘으로 숫자 데이터 타입으로 차 있는 배열을 오름차순으로 정렬하기와 같은 예가 있다.

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

배열의 길이 만큼 반복을 하기 때문에 시간 복잡도는 O(N^2)을 가진다.

✍ 버블 정렬 (Bubble Sort)

버블 정렬은 가장 간단하게 구현할 수 있는 정렬 중 하나이며, 주어진 배열의 각 요소를 순환하면서 각 요소의 옆 요소와 비교 및 검사를 실행하여 적은 값은 왼쪽, 더 큰 값은 오른쪽으로 swap하는 알고리즘이다,

function bubbleSort(array) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < array.length; i++) {
      if (array[i] > array[i + 1]) {
        let temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return array;
}

이것도 배열의 길이 만큼 반복되기 때문에 시간 복잡도는 최대 O(N^2)을 가진다.

📝 버블 정렬과 선택 정렬의 차이점

언뜻, 보면 선택 정렬과 버블 정렬이 같은 것으로 보일 수 있으나 다음과 같은 차이를 가지고 있다.

• 버블 정렬은 swap 선택 정렬은 전체적인 정렬에 가깝다.
• 버블 정렬은 반복되는 요소를 입력 때와 동일한 순서로 정렬하기에 더욱 안정적인 알고리즘
• 버블 정렬은 선택 정렬에 비해 느리고 비효율적

✍ 삽입 정렬 (Insertion Sort)

삽입 정렬은 말 그대로 삽입 하는 것으로, 2번째 요소부터 좌쪽과 비교하며 자신의 위치에 맞는 위치에 요소를 끼워 넣는 것이다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let current = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > current) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = current;
  }
  return array;
}

삽입 정렬은 버블 정렬과 비슷하게 안정적인 알고리즘이며 시간 복잡성은 최대 O(n^2)을 가진다.

✍ 퀵 정렬 (Quick Sort)

퀵 정렬은 위에 불안정적인 알고리즘 중 하나로 Divide and Conquer 방식을 택하여 요소들 중 하나를 피벗(Pivot)으로 설정하고 그것보다 작은 요소들은 좌측으로 큰 것들은 우측으로 옮긴 후 분할을 한 다음 그 결과 값 내에서 다시 퀵 정렬이 실행되고 분할 된 구역의 크기가 0 또는 1이 될 때까지 반복하여 정렬 후 분할 된 요소들을 합친다.

const quickSort = function (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]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

퀵 정렬은 일반적으로 좋은 성능을 보여주는데 최고의 경우 시간 복잡도는 O(nlog_2 n)을 가지지만 최악의 경우 O(n^2)를 가진다.

✍ 병합 정렬 (Merge Sort)

병합 정렬도 퀵 정렬과 함께 자주 사용되는 정렬 법 중 하나이며 퀵 정렬과 마찬가지로 Divide and Conquer 방식을 채택하여 요소들을 정렬 하고 있다.

하지만 차이가 있다면 병합 정렬은 Pivot을 설정하지 않고 무조건 요소들을 반으로 잘라 하나의 요소가 남을 때 까지 자른 뒤 다시 합치는 과정에서 정렬을 한다.

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

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

병합 정렬은 어떤 상황에서도 무조건 반으로 쪼갠 후 연산을 수행하기 때문에 N*log(N)의 시간 복잡도를 보장할 수 있지만 추가 메모리 공간이 필요 하기 때문에 메모리 낭비가 있을 수 있다.

✍ 힙 정렬 (Heap Sort)

자료구조 중 하나인 힙(Heap)을 이용해 정렬을 한다.

function heapSort(array) {
  for (let i = Math.floor(array.length / 2); i >= 0; i--) {
    heapify(array, array.length, i);
  }

  for (let i = array.length - 1; i > 0; i--) {
    let temp = array[0];
    array[0] = array[i];
    array[i] = temp;

    heapify(array, i, 0);
  }

  return array;
}

function heapify(array, size, root) {
  let largest = root;
  let left = 2 * root + 1;
  let right = 2 * root + 2;

  if (left < size && array[left] > array[largest]) {
    largest = left;
  }

  if (right < size && array[right] > array[largest]) {
    largest = right;
  }
 
  if (largest !== root) {
    let temp = array[root];
    array[root] = array[largest];
    array[largest] = temp;
    heapify(array, size, largest);
  }
}

주어진 배열을 힙 구조로 우선 만들어야 하기 때문에 시간복잡도 + 힙 정렬을 하는 시간복잡도 = N _ log(N) + N _ log(N) = N * log(N)

✍ 계수 정렬 (Heap Sort)

계수 정렬은 데이터 값들이 양수이며 값의 범위가 상대적으로 작은 곳에 적용해야 효율적으로 뽑아 낼 수 있는 알고리즘이다.

function countingSort(array, max) {
  let counts = new Array(max + 1).fill(0);
  for (let i = 0; i < array.length; i++) {
    counts[array[i]]++;
  }

  let sortedIndex = 0;
  for (let i = 0; i < counts.length; i++) {
    while (counts[i] > 0) {
      array[sortedIndex] = i;
      sortedIndex++;
      counts[i]--;
    }
  }

  return array;
}

계수 정렬은 위에 언급한 제약 조건만 만족한다면 O(N)의 시간 복잡도를 가진다.

정렬 알고리즘 이외에도 몇 개 더 있는 것 같아 보이지만..사실 아직까지 다양하게 적용해본적이 없기에 여기서 마무리하고 추후 딥 다이브하게 되면 하나 하나 파 볼 예정이다.