정렬 알고리즘 종류

1. Bubble sort

• 정의: 서로 인접한 두 원소의 대소 비교 후, 조건에 따라 swap
• 시간 복잡도: (n-1) + (n-2) + ... + 1 = O(n^2)
• 공간 복잡도: 주어진 배열 안에서 swap = O(n)
• 특징: stable sort, In-place Algorithm

stable sort
배열 속 중복된 값을 가진 요소들이 정렬 후, 순서가 변하지 않는 경우

In-place Algorithm
정렬을 하면서 추가적인 메모리 공간 거의 필요없는 경우

2. Selection Sort

• 정의:
  • 원소를 넣을 순서(index)는 정해져 있고, 어떤 원소를 넣을지 선택하는 정렬
  • i번째 원소를 포함한 나머지 배열에서 최솟값 찾고 -> 최솟값과 i번째 원소 swap -> i+1번째 원소에 대해 똑같이 진행
• 시간 복잡도: (n-1)+(n-2)+...+1 = O(n^2)
• 공간 복잡도: bubble sort 와 동일
• 특징: Unstable, In-place

3. Insertion Sort

• 정의:
  • Selection Sort와 달리 현재 index 보다 낮은 부분의 탐색한다 -> 이미 정렬된 부분을 이용해 시간을 줄인다.
  • 현재 index의 값을 temp에 저장한다. -> index보다 1 낮은 prev 라는 값을 생성한다. -> prev에 해당하는 값이 temp 보다 처음으로 작거나 같은 위치를 찾는다 -> prev가 투 포인터 처럼 이동하는 과정에서, 배열의 모든 요소를 앞으로 당기는 arr[prev + 1] = arr[prev] 과정을 거친다.-> 마침내 도착한 prev + 1은 temp보다 큰 요소의 위치면서, 인덱스가 가장 작은 위치이다. -> 따라서 prev + 1 위치에 temp를 넣고 -> index를 한칸 올린 후 같은 과정을 진행한다.
  • 이 과정은 index 이하의 부분 배열에서, arr[index] 요소를 추출 후 -> 적절한 위치에 삽입하는 과정과 같다. => 배열의 삽입은 O(n) -> 그러나, 적절한 위치가 자신의 위치와 같다면 -> 배열 삽입 x -> O(1)
• 시간 복잡도: O(n^2), 모두 정렬 돼 있을 때 -> O(n)
• 공간 복잡도: O(n)
• 특징: stable, in-place

4. Quick Sort

• 정의:
  • pivot 을 기준으로 작은 것은 왼쪽, 큰 것은 오른쪽으로 옮기는 아이디어(ascending 기준)
  • 이때 pivot 은 배열을 마지막 항으로 함
  • pivot 과 비교하는 값은 배열의 첫 번째 요소부터 시작
  • 값이 pivot 보다 클 경우, pivot 오른편으로 옮김, 이때 비교하는 값의 인덱스 고정
  • 값이 pivot 보다 작을 경우, 변화없고 비교하려는 값의 인덱스 +1
  • 비교하려는 인덱스와 pivot의 인덱스가 같아지면 partitioning 종료
  • pivot 에 대해 partitioning 이 끝난 경우, pivot 은 고정하고, 각 partition의 마지막 요소를 각각의 pivot으로 생각해 반복
  • 주의할 점: 배열의 크기가 정해는 in-place sort 이기 때문에, pivot 기준 오른쪽으로 옮기는 작업은 다음과 같은 제약을 가짐
    • pivot의 index 는 index -= 1
    • 옮기려는 값은 index로 이동
    • index - 1 에 있던 값은 옮긴 값의 위치로 감
• 종류: Quick Sort 는 partitioning 방법에 따라 2가지 종류가 있다.
  1. Lomuto’s Partition: 위의 설명처럼 pivot을 배열의 마지막으로 설정
  2. Hoare’s Parition: 배열의 중간값을 pivot으로 설정
• 시간 복잡도
  • 최선의 경우: partitioning 이 잘 될 경우 = pivot 의 위치가 (배열의 길이 / 2) 경우 = O(nlogn)
  • 최악의 경우: partitioning 이 잘 안 될 경우 = pivot 의 위치가 배열의 길이 - 1 or 0일 경우 = O(n^2)
• 특징: unstable, in-place

// Lomuto’s Partition 구현
const partition = (arr, start, end) => {
  const pivotValue = arr[end]
  let upperPivotIdx = start
  for (let index = start; index < end; start++) {
    if (arr[index] < pivotValue) {
      ;[arr[index], arr[upperPivotIdx]] = [arr[upperPivotIdx], arr[index]]
      upperPivotIdx += 1
    }
  }
  ;[arr[end], arr[upperPivotIdx]] = [arr[end], arr[upperPivotIdx]]
  return upperPivotIdx
}

5. Merge Sort

• 정의:
  • 배열을 반으로 쪼개고, 나뉘어진 부분도 반으로 계속 쪼갬
  • 쪼개진 요소의 length 가 1 일 때 까지 쪼갬
  • 그 이후, 쪼개진 쌍을 서로 비교하여 정렬함
  • 재귀적으로 반복
  • 전체 프로세스는 2*logn 번, 각 프로세스는 n번의 탐색이 이루어짐 (각 부분들은 정렬이 되어 있으므로)
• 시간 복잡도: O(nlogn)
• 공간 복잡도: n번의 재귀호출 -> O(n)
• 특징
  • LinkedList에서 편리: merge 할 때, 새로운 배열 만들 필요없이 삽입하면 됨, Quick Sort의 경우 in-place이기 때문에 배열 인덱스 중요 -> LinkedList는 좋은 선택 아님
  • stable
• 장점: 정렬된 배열에서는 merge 가 더 빠르고, 최선과 최악의 시간 복잡도가 같다.
• 구현
  • divide: 배열을 반으로 쪼개는 함수
  • merge: 쪼개진 배열을 sort 하며 합치는 함수

const merge = (left, right) => {
  const mergedArr = []
  // 정렬 -> O(n)
  while (left.length !== 0 && right.length !== 0) {
    if (left[0] <= right[0]) mergedArr.push(left.shift())
    else mergedArr.push(right.shift())
  // 최선: O(n/2), 최악: O(n)
  return [...mergedArr, ...left, ...right]
}

const divide = (arr) => {
  // 정지 조건
  const length = arr.length
  if (length === 1) return arr

  const mid = Math.floor(length / 2)
  const left = arr.slice(0, mid)
  const right = arr.slice(mid)

  return merge(divide(left), divide(right))
}