[JavaScript] Quick Sort(퀵 정렬)

Quick Sort(퀵 정렬)의 개념

1. 초기 배열

 

2. 초기 배열의 첫 번째 요소를 pivot으로 잡는다.

3. pivot을 가운데로 옮긴다. 그리고 pivot보다 작은 요소들을 왼쪽, 큰 요소들은 오른쪽으로 이동시킨다.

4. 초기 pivot은 고정시키고 양쪽 배열들의 첫 요소를 pivot으로 잡는다.

5. pivot들을 가운데로 이동시킨다. 그리고 작은건 왼쪽, 큰건 오른쪽으로 이동시킨다.

6. 3, 7 pivot은 고정시키고 그 양쪽으로 갈라진 배열들의 첫 요소를 pivot으로 잡는다.

 

7. pivot을 중심으로 좌우로 이동시키고 이동시킬 요소가 없는 pivot은 고정 시킨다.

8. 고정되지 않은(pivot이 한번도 아니었던) 1, 6, 9번

 

9. 1, 6, 9번을 pivot으로 잡았지만 움직일 곳이 없어 고정시킨다.

10. 고정된 배열

 

11. 최종 배열

 

Quick Sort(퀵 정렬) 구현 소스 코드

function quickSort(arr) {
  // arr의 요소가 하나이면 arr 자체를 그대로 반환
  if(arr.length < 2) {
    return arr;
  };

  // quickSort 초기 배열을 선언 첫 pivot 배열의 첫 번째 요소이다.
  let pivot = [arr[0]];
  let left = [];
  let right = [];

  // for문을 돌면서 pivot보다 작은 것은 왼쪽 큰 것은 오른쪽 그렇지 않은 것은 pivot에 넣어준다.
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] < pivot) {
      left.push(arr[i]);
    } else if(arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      pivot.push(arr[i]);
    }
  }
  // quickSort 진행상황을 단계별로 보여주기 위한 코드
  console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`);

  // 재귀함수 구조로 다시 선언해서 끝날때까지 시작한다.
  return quickSort(left).concat(pivot, quickSort(right));
}

 

  위 그림과 같은 배열 [4, 3, 7, 8, 5, 2, 1, 6, 9, 4]의 Quick Sort 실행 결과

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

// left: 3,2,1, pivot: 4,4, right: 7,8,5,6,9
// left: 2,1, pivot: 3, right: 
// left: 1, pivot: 2, right:
// left: 5,6, pivot: 7, right: 8,9
// left: , pivot: 5, right: 6
// left: , pivot: 8, right: 9
// 최종 배열
// [1, 2, 3, 4, 4, 5, 6, 7, 8, 9]

 

 

Quick Sort의 시간복잡도

  Quick Sort를 사용하는 이유는 시간복잡도가 가장 효율적으로 빠르기 때문이다. 퀵 정렬 알고리즘은 기본적으로 n번씩 탐색하지만 반으로 나누면서 들어간다. 즉, 평균적으로 O(n*logn)의 시간 복잡도를 가진다. 하지만 최악의 경우 n^2이 되는 정렬이 되기도 한다. 1, 2, ,4 ,5 ,6, 7, 8, 9, 10 같이 나란히 있는 숫자에서는 큰 복잡도를 가진다. 따라서 데이터의 특성에 따라 어떠한 정렬 방식을 쓸지 정하는 것이 중요하다.