[알고리즘 정리] 01. 정렬

📌 이번시간에는 정렬 알고리즘에 대해 정리를 할 것 이다.

왜? 평소에 정렬을 하면 js가 지원하는 sort만 썼지, 내부적으로 어떻게 돌아가는지 알고 싶어서 이번기회에 정리를 하겠다.

정렬

1. 선택정렬(Selection Sort)

정렬중에서도 가장 기본적인 정렬이다.
"가장 작은 값"을 찾아 맨 앞으로 보내고, fix시키고, 그 다음 작은 값을 두번쨰로 보내고 fix시키고.... 이 과정을 반복해서 정렬하는 방식이다.

시간복잡도 : O(n^2)

코드

const SelectionSort = arr => {
  let arrs = arr;
  for (var i = 0; i < arrs.length; i++) {
    let min = 9999;
    let idx = 0;
    let tmp;
    for (var k = i; k < arrs.length; k++) {
      if (min > arrs[k]) {
        min = arrs[k];
        idx = k;
      }
    }

    tmp = arrs[i];
    arrs[i] = min;
    arrs[idx] = tmp;
  }
  console.log(arrs);
};

SelectionSort([1, 10, 5, 4, 19, 20, 25, 30, 20]);

2. 버블정렬(Bubble Sort)

오름차순으로 정렬한다고 가정하였을 때, 인접한 두 값 사이에서 작은 값을 앞으로 보내는 방식이다. 선택정렬과 다르게, 순회하면서, 바로바로 값의 위치를 바꿔준다.

시간복잡도 : O(n^2)

코드

const BubbleSort = arr => {
  let arrs = arr;
  for (var i = 0; i < arrs.length; i++) {
    for (var k = i; k < arrs.length - 1; k++) {
      if (arrs[k] > arrs[k + 1]) {
        let tmp = arrs[k];
        arrs[k] = arrs[k + 1];
        arrs[k + 1] = tmp;
      }
    }
  }
  console.log(arrs);
};
BubbleSort([1, 9, 15, 32, 49, 30, 5959, 30]);

⭐️ 3. 퀵정렬(Quick Sort)

앞서 말한 정렬방법들은 모두 시간복잡도가 O(n^2)로써 데이터개수가 10만개 이상이면 실제로 쓰기 어려운 정렬이다.
지금 소개하는 퀵정렬은 평균 시간복잡도가 O(n*logn)로써 대표적인 "분할정복" 기법이다.

Q) 분할정복(Divide and Conquer)이란?
A) 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

예를 들어, [3, 1, 9, 7, 5] 라는 배열이 존재한다고 하자.
피벗은 대게 첫번째 원소로 잡는다. 여기서 피벗은 "3"이므로, 3보다 작은 값들을 왼쪽으로, 큰 값은 오른쪽으로 나눈다

1. left = [1], pivot = 3, right = [9, 7, 5]
   left는 배열의 길이가 2미만이므로, fix !!

2. 이제 right에 대하여 재귀적으로 수행하자! pivot은 "9"
   left = [7, 5], pivot = 9, right = []
   right는 빈 배열이므로 fix!!

3. 남은 left에 대하여 수행하면
   left = [5], pivot = 7, right = []

따라서, [1, 3, 5, 7, 9] 배열로 오름차순 정렬이 완료된다.

시간복잡도 : O(n * logn)

코드

const QuickSort = arr => {
  let arrs = arr;
  if (arrs.length < 2) {
    return arrs;
  }
  let pivot = [arr[0]];
  let left = [];
  let right = [];
  for (var i = 1; i < arrs.length; i++) {
    if (arrs[i] > pivot) right.push(arrs[i]);
    else if (arrs[i] < pivot) left.push(arrs[i]);
    else pivot.push(arrs[i]);
  }
  return [...QuickSort(left), ...pivot, ...QuickSort(right)];
};

console.log(QuickSort([1, 4, 9, 9, 10, 54, 32, 45, 33, 7]));