Algorithm JS - 퀵 정렬

목차

• 퀵 소트
• Big O
• 알고리즘
• 퀵 소트 구현

퀵 소트

• 피벗을 기준으로 목록을 큰 값과 작은 값으로 나누어 정렬하는 기법
• 불안정 정렬 중 하나
• 분할 정복 알고리즘으로, 평균적으로 매우 빠른 수행 속도의 정렬이 가능

Big O

Best Case

• O(nlogn)

Worst Case (이미 정렬된 배열을 정렬하는 경우)

• O(n^2)

장점

• 매우 빠르며 대표적인 분할 정복 알고리즘

단점

• 별도의 메모리 공간을 필요로 하여 공간적 낭비가 심함(unstable)

알고리즘

1. 배열 안 원소가 1개 일 경우 return
2. 아닐 경우 pivot, Left, Right 설정
3. arr[Left] > arr[pivot] or Left >= end일 경우 종료 아닐 경우 lp 1증가
4. arr[rp] < arr[pivot] or Right >= start일 경우 종료 아닐 경우 Right 1증가
5. 종료 됬는데 만약 lp와 rp가 교차 되는 경우 arr[pivot]과 arr[Right] 값 교체
6. 종료 됬는데 만약 교차 되지 않을 경우 arr[Left]와 arr[Right] 교체
7. 재귀를 통해 피벗 보다 작은 값 and 큰 값 모여 있는 arr를 반복 호출 후 원소가 1개일 경우 함수 return

퀵 소트 구현

const array = [2, 1, 3, 4, 5];

function quickSort(arr, start, end) {
  // 원소가 1개일 경우 종료
  if (start >= end) return;

  // 배열의 첫 번째 원소 = 피벗, 피벗 다음 값 = left, 배열의 마지막 요소 = right
  let pivot = start;
  let left = start + 1;
  let right = end;

  // left가 right보다 작거나 같을 경우 종료
  while (left <= right) {
    while (arr[pivot] > arr[left] && left <= end) left += 1;
    while (arr[pivot] < arr[right] && right >= start) right -= 1;
    if (left > right) {
      [arr[pivot], arr[right]] = [arr[right], arr[pivot]];
    } else {
      [arr[right], arr[left]] = [arr[left], arr[right]];
    }
  }
  // 재귀 호출[(0~ 피벗 보다 1작은 요소 까지의 배열), (피벗보다 1큰 요소~ 배열길이 끝까지의 배열)]
  quickSort(arr, 0, right - 1);
  quickSort(arr, right + 1, end);

  // 종료 될 경우 정렬된 arr 반환
  return array;
}

const answer = quickSort(array, 0, array.length - 1);

console.log(answer);