[알고리즘] 퀵 정렬 (Quick Sort)

 퀵 정렬 (Quick Sort) 

1. 퀵 정렬이란?

퀵 정렬(quick sort) 역시 병합 정렬과 마찬가지로 어떤 문제를 2개의 작은 문제로 분리해 각각을 해결하는 분할 정복 알고리즘 중 하나다.

 

1-1) 차이점

1. 병합 정렬
   - 분할 단계에서는 분할만 하고 병합 단계에서 정렬을 한다
2. 퀵 정렬
   - 분할 단계에서 정렬이 이루어지며, 병합 시에는 병합만 한다.

 

퀵 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다.

• 분할 (Divde) : 입력된 배열을 기준점(pivot)을 기준으로 비균등하게 분할한다.
• 정복 (Conquer) : 분할된 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 1이 아니면) 순환 호출을 이용하여 다시 분할한다.
• 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다.

 

퀵 정렬은 다음 단계들로 진행된다.

• 배열 내에서 기준에 되는 요소 하나를 선택한다. 이 기준이 되는 요소가 피벗(pivot, 기준점)이다.
  - 배열의 1번째 요소, 마지막 요소, 중앙에 위치한 요소가 pivot이 될 수 있다
• pivot보다 작은 요소들은 pivot의 왼쪽으로, 큰 요소들은 pivot의 오른쪽으로 옮겨진다.
  - pivot이 정중앙 요소일 때, 맨 왼쪽 요소의 인덱스를 i, 맨 오른쪽 요소의 인덱스를 j로 둔다
  - i가 커지면서 i번째 값을 pivot과 비교하고, j는 점차 작아지면서 j번째 값을 pivot과 비교하여 정렬한다
  - 제대로 정렬되어 있을 때는 인덱스 값만 증가/감소 시켜준다 (i번째 값이 pivot보다 작고, j번째 값이 pivot보다 클때)
• i값이 j값보다 커졌을 때 이 과정을 멈추고 이때의 i 값을 반환해주며, 이 i값을 기준으로 2개의 배열로 나눠 각 배열을 위와 같은 방식으로 재귀 호출하여 정렬해준다.
• 더이상 잘라줄 수 없을때, 이 과정을 멈춰준다.

 

예시를 통해 살펴보자.

1. 정렬되지 않은 배열의 중간값 7을 pivot으로 정해준다.
2. 맨 왼쪽과 맨 오른쪽의 인덱스 값부터 시작하여 중앙으로 오면서 pivot 값과 비교해준다.
   - 왼쪽의 인덱스는 i, 오른쪽의 인덱스는 j
3. 왼쪽에는 pivot보다 작은 값이 와야하고, 오른쪽에는 pivot보다 큰 값이 와야하지만, 그러지 않은 경우가 나올때까지 인덱스를 이동해준다.
   - 1은 7보다 작기 때문에 그대로 두고 인덱스 i만 증가시켜준다
4. 그렇지 않은 경우가 왼쪽에서는 12, 오른쪽에서는 2가 나왔을때, 두 값의 자리를 서로 바꿔준다.
5. 이렇게 교환을 해주다가 i의 값이 j보다 커졌을 때 이 과정을 멈추고, 이때의 i값 5를 반환해주고, 5를 기준으로 배열을 나눠준다.

 

728x90

 

---

2. 퀵 정렬 구현 코드

위와 같은 과정을 구현한 코드는 다음과 같다.

function quickSort(arr, left, right) {
  if (left >= right) {
    return;
  }
  // 기준점
  const mid = Math.floor((left + right) / 2);
  const pivot = arr[mid];
  const partition = divide(arr, left, right, pivot);

  quickSort(arr, left, partition - 1);
  quickSort(arr, partition, right);

  return arr;
}

function divide(arr, left, right, pivot) {
  while (left <= right) {
    while (arr[left] < pivot) {  // pivot과 비교
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }

    if (left <= right) {   // 왼쪽 값과 오른쪽 값을 바꾸기
      let tmp = arr[left];
      arr[left] = arr[right];
      arr[right] = tmp;
      left++;
      right--;
    }
  }
  return left;
}

 

---

위 코드를 좀 더 이해하기 쉽게 하기 위해 중간중간  console.log() 로 각각의 값들을 찍어보기로 했다.

 

const arr = [7, 3, 5];

function quickSort(arr, left, right) {
  if (left >= right) {
    return;
  }
  // 기준점
  const mid = Math.floor((left + right) / 2);
  const pivot = arr[mid];
  const partition = divide(arr, left, right, pivot);

  console.log(`왼쪽 - left: ${left}, partition-1: ${partition-1}, right: ${right}`)
  quickSort(arr, left, partition - 1);
  console.log(`오른쪽 - partition: ${partition}, left: ${left}, right: ${right}`)
  quickSort(arr, partition, right);

  return arr;
}

function divide(arr, left, right, pivot) {
  console.log(`[${arr}], left: ${left}, right: ${right}`);
  while (left <= right) {
    while (arr[left] < pivot) {  // pivot과 비교
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }

    if (left <= right) {   // 왼쪽 값과 오른쪽 값을 바꾸기
      let tmp = arr[left];
      // console.log(`pivot: ${pivot}, left: ${left}, right: ${right}, tmp: ${tmp}`)
      arr[left] = arr[right];
      arr[right] = tmp;
      left++;
      right--;
    }
  }
  console.log(`반환값: ${left}, arr: [${arr}]`)
  console.log('---------------------')
  return left;
}

console.log(quickSort(arr, 0, arr.length -1));

[7, 3, 5]를 넣었을 때, 콘솔창 결과는 다음과 같다.

1. 먼저, quickSort() 함수에 left는 0, right는 2, pivot는 3로 시작한다.
   - partition에 할당되는 divide() 함수에 [7, 3, 5]와 0, 2가 입력된다.
   - divide() 함수에서 기준점 3을 기준으로 왼쪽을 먼저 살펴보고 3과 7의 자리가 바뀌고([3, 7, 5]) 1을 반환해준다.
   - partiton 1
2. quickSort(arr, left, partition -1) 함수를 통해 pivot의 왼쪽을 살펴본다.
   - quickSort([3, 7, 5], 0, 0)은 더이상 분할할 수 없으므로 종료된다.
3. quickSort(arr, partition, right) 함수를 통해 pivot의 오른쪽을 살펴본다.
   - quickSort([3, 7, 5], 1, 2)는 partition에 할당될 divide() 함수에 [3, 7, 5], 1, 2를 입력해준다.
   - divde() 함수는 pivot 7을 기준으로 7과 5를 비교하여 7과 5의 자리를 바꿔주고([3, 5, 7]), 2를 반환해준다.
   - partition 2
4. quickSort([3, 5, 7], 1, 1)와 quickSort([3, 5, 7], 2, 2)
   - quickSort([3, 5, 7], 1, 1)로 더이상 분할할 것이 없으므로 종료한다. 
   - quickSort([3, 5, 7], 2, 2)는 더이상 오른쪽에서 분할할 것이 없으므로 종료된다.
5. 최종적으로, 정렬된 [3, 5, 7]을 반환해준다.

[7,3,5], left: 0, right: 2
반환값: 1, arr: [3,7,5]
---------------------
왼쪽 - left: 0, partition-1: 0, right: 2
오른쪽 - partition: 1, left: 0, right: 2
[3,7,5], left: 1, right: 2
반환값: 2, arr: [3,5,7]
---------------------
왼쪽 - left: 1, partition-1: 1, right: 2
오른쪽 - partition: 2, left: 1, right: 2
[ 3, 5, 7 ]

 

반응형

 

---

3. 퀵 정렬의 장단점

장점

1.  속도가 빠르다
   - 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
2. 추가 메모리 공간을 필요로 하지 않는다
   - 퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다

단점

1. 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸릴 수 있다
   Ex> 오름차순 배열 -> 내림차순 정렬 / 내림차순 배열 - 오름차순 정렬
   - 불균형 분할을 방지하기 위해 pivot을 중간 값(medium)을 선택할 수 있다

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://evan-moon.github.io/2018/10/13/sort-algorithm/#퀵정렬quick-sort
• https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
• https://nyang-in.tistory.com/222
• https://gyoogle.dev/blog/algorithm/Quick%20Sort.html