퀵 정렬이 무엇일까

Pivot#

pivot이라는 helper함수를 만들어 줄 것 입니다 배열의 첫번 째 값을 기준값으로 두고 왼쪽에는 작은 값 오른쪽에는 큰 값을 두었을때 기준값이 처음 배열에서 몇 번재 인덱스 자리에 이썽야하는지를 반환합니다

코드로 보겠습니다

1
function pivot(arr, start = 0, end = arr.length - 1) {
2
  function swap(arr, i, j) {
3
    const temp = arr[i];
4
    arr[i] = arr[j];
5
    arr[j] = temp;
6
  }
7
  let pivot = arr[start];
8
  let swapIndex = start;
9

10
  for (let i = start + 1; i < arr.length; i++) {
11
    if (pivot > arr[i]) {
12
      swapIndex++;
13
      swap(arr, swapIndex, i);
14
    }
15
  }
16
  swap(arr, start, swapIndex);
17
  return swapIndex;
18
}

예시로 pivot이라는 함수가 어떻게 동작하는지 설명 드리겠습니다 예시는 [4,6,7,2,1,5,9,3] 배열로 하겠습니다

현재의 pivot값으로 첫번째 값 4 저장해둡니다 swapIndex를 인자로 들어오는 start로 둡니다

루프를 시작하여 pivot값이 arr[i]값 보다 크다면 swapIndex을 올린뒤 swap합니다 루프가 끝나면 pivot이 있어야할 위치인 swapIndex와 swap합니다

차근차근 값이 어떻게 움직이는 지 보겠습니다

1. 기준값은 첫번째 값인 4로 시작합니다
2. 루프를 시작합니다
3. 2는 4보다 작으니 swapIndex을 1 올려주고 6과 자리를 바꿔 줍니다 [4,2,7,6,1,5,9,3]
4. 1은 4보다 작으니 swapIndex을 1 올려주고 7과 자리를 바꿔 줍니다 [4,2,1,6,7,5,9,3]
5. 3은 4보다 작으니 swapIndex을 1 올려주고 6과 바꿔줍니다 [4,2,1,3,7,5,9,6]
6. 루프가 종료되어 swapIndex와 start index 자리를 swap합니다 [3,2,1,4,7,5,9,6]

QuickSort#

코드로 먼저 보겠습니다

1
function quickSort(arr, left = 0, right = arr.length - 1) {
2
  if (left < right) {
3
    const pivotIndex = pivot(arr, left, right);
4
    quickSort(arr, left, pivotIndex - 1);
5
    quickSort(arr, pivotIndex + 1, right);
6
  }
7
  return arr;
8
}

pivot helper 함수를 이용하여 첫번째 값이 어디 index으로 가야할지 구합니다 그 값을 기준으로 앞 뒤로 나누어 정렬을 게속하게됩니다 위의 로직이 계속 실행되어 정렬된 arr배열을 반환하게 됩니다

한동룡