퀵정렬

퀵정렬이란

퀵정렬은 분할 정보 알고리즘의 한 종류이며 피벗(pivot)을 지정해서 그 기준으로 정렬하는것
정렬한 후에 분할된 배열에 대해 다시 한번 피벗을 지정해서 정렬하는 것을 반복한다(재귀적 함수 호출)

시간복잡도

피벗을 어떻게 선택하느냐에 따라 실행시간이 달라질수 있음(보통 처음, 마지막, 중간)

• 최악의 경우 n^2
• 평균으로 nlogn

퀵 정렬 예시

5,1,3,7,8,2,4,6 오름차순 정렬, pivot은 첫번째

1. 5 기준 왼쪽[1,3,2,4] 오른쪽[7,8,6]
2. 각 부분 배열에서 재귀적으로 반복 pivot1 [][3,2,4] pivot3 [2][4] 결합: 2+3+4

퀵 정렬 코드

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

  const pivot = arr[0]; // 첫 번째 원소를 피벗으로 선택
  const leftArr = [];
  const rightArr = [];

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

  // 왼쪽과 오른쪽 부분배열에 대해 재귀적으로 quickSort 함수 호출
  **return quickSort(leftArr).concat(pivot, quickSort(rightArr));**
}

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

퀵정렬 장 단점

• 장점
  • 평균적으로 nlogn의 실행시간을 가진다(빠름)
  • 구현이 간단
• 단점
  • 최악의 경우 n^2 일수 있다(이미 정렬이 되어있는 경우)
  • 동일한 값의 상대적인 위치가 변경될 수 있어서 불안정적이다
  • 피벗에 따라 실행시간이 달라진다.

https://hongjw1938.tistory.com/192
https://www.toptal.com/developers/sorting-algorithms/quick-sort