알고리즘 - 퀵 정렬(Quick Sort)

 

퀵 정렬 (Quick Sort)이란

퀵 정렬은 특정 원소(피벗) 기준으로 주어진 배열을 두 부분 배열로 분할한 뒤,

각 부분 배열에 대해서 퀵 정렬을 순환적(재귀적)으로 적용하는 방식이다

 

퀵 정렬은 최악의 경우 시간 복잡도 O(n²) 이고 평균적인 시간 복잡도는 O(nlogn) 이다.

최악의 경우는 피봇이 배열의 맨 처음 혹은 마지막으로 쏠려 일어나는 불균형적인 분할인 상황이며,

최선의 경우는 피봇이 정확히 n/2크기로 분할되는 균형적인 분할로 볼 수 있다.

하지만 피봇의 임의성만 보장된다면 평균성능 O(nlogn) 의 가능성이 매우 높게 된다.

 

퀵 정렬을 분할 정복 단계로 본다면

분할: 피벗을 기준으로 주어진 배열을 두 부분 배열로 분할한다.

정복: 두 부분배열에 대해서 퀵정렬을 순환적으로 적용하여 각 부분배열을 정렬한다.

 

 

QuickSort : 퀵정렬 함수

quickSort 함수의 매개 변수로는 arr 과 n 을 받는다

arr 는 미정렬된 배열을 의미하고 n 은 배열 원소의 갯수이다

결과로 정렬된 배열이 리턴 된다

function quickSort (arr) {    
  if(arr.length <= 1){ // 배열의 원소가 1개 이하인 경우
    return arr;        // 있는 그대로 반환
  }
  
  const pivot = partition(arr); // partition 함수를 통해 피봇 인덱스 설정
  const leftArr = arr.slice(0, pivot);   // 피봇 이전의 배열
  const rightArr = arr.slice(pivot + 1); // 피봇 이후의 배열
  
  // 분할된 배열을 재귀적으로 정렬하고 합쳐서 반환
  return [...quickSort(leftArr), arr[pivot], ...quickSort(rightArr)];
}

 

 

 

Partition : 퀵정렬 분할함수 

quickSort 함수의 매개 변수로는 arr 과 n 을 받는다

arr 는 분할할 배열을 의미하고 n 은 배열 원소의 갯수이다

결과로 피벗의 인덱스를 리턴한다

function partition (arr) {
  let left = 0;      // 배열의 구간 시작점 표현 (첫번째 인덱스를 의미)
  let right = arr.length - 1; // 배열의 구간 마지막점 표현 (마지막 인덱스를 의미)
  let pivot = arr[0];// 피봇을 배열의 첫번째 요소로 설정

  while(left < right) {
    // left 가 arr.length 보다 작고, 첫번째 원소값이 pivot 보다 작을 때 실행
    while(left < arr.length && arr[left] < pivot) {
      left++; // 맨앞에서는 한칸식 전진
    }

    // right 인덱스가 0보다 크고, pivot이 배열의 마지막 원소값 보다 작거나 같을 때 실행
    while(0 < right && pivot <= arr[right]) {
      right--; // 맨끝에서는 한칸씩 후진
    }

    // 즉 배열 범위 안에서 탐색중인 경우
    if(left < right){
      // arr[left] 과 arr[right] 의 원소를 서로 교환
      let temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
    } else {
      break;
    }
  }

  // 범위 바깥으로 나간 경우
  // arr[0] 과 arr[right] 의 원소를 서로 교환 후 right를 다음 피봇 인덱스로 선정
  let temp = arr[0];
  arr[0] = arr[right];
  arr[right] = temp;

  return right;
}