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

 목  차

• 퀵 정렬(Quick Sort)
• 기본 개념
• 퀵 정렬을 구현하며 배운 것들
• 구현 방법

 

 

---

 

  퀵 정렬(Quick Sort) 기본 개념

 

퀵 정렬은 분할 정복 전략(Divide and Conquer)을 사용한다. 평균 O(n log n)의 시간 복잡도를 가지고, 최악의 경우(정렬된 배열) O(n^2)의 시간 복잡도를 가진다.

 

pivot 을 먼저 선택하고 그 pivot을 기준으로 더 큰 값과 더 작은 값을 분류한다. 이 것을 '파티셔닝'이라고 하며, 재귀적으로 정렬을 한다.

 

 

  pivot 의 중요성 

 

퀵 정렬에서 pivot 은 시간 복잡도에 큰 영향을 끼친다. 일반적으로 첫 번째 인덱스, 중간 인덱스, 마지막 인덱스를 pivot 으로 설정한다.

 

 

 

pivot == 마지막 인덱스

 

---

 

    퀵 정렬을 구현하며 배운 것들

 

내가 알고 있던 개념들을 사용하였기에 기술적으로 새로 배운 것들은 없는 것 같다.

 

하지만 중간 인덱스를 사용하고 싶다는 내 욕심이 구현을 더 복잡하게 했던 것 같다. 처음부터 '첫 번째 인덱스를 사용해서 정렬을 하면 쉽겠는데?'라는 생각이 있었지만 더 욕심을 내서 중간 값으로 해보자고 생각했지만, 처음 퀵 정렬을 구현하는 입장에서 조금 과했던 것 같다. 

 

 

  중간 인덱스로 구현을 시도하며 문제가 되었던 것

 

중간 인덱스로 구현을 하면 포인터가 pivot을 지나가는 상황이 발생한다. 이 경우에 pivot 의 위치를 보호해 주어야 한다.

한 마디로 예외처리가 필요하다고 생각한다.

 

근데 생각해 보니까 처음 인덱스 혹은 마지막 인덱스를 사용하면 이런 예외처리가 필요가 없어진다!

 

 

(그래서 중간 인덱스로 구현을 하는 것은 나중에 다시 시도해 보지만, 일단 퀵 정렬을 공부하게 된 계기인 볼록 껍질(Convex Hull) 문제를 풀고 난 뒤에 하려고 한다.) 

 

 

 

---

 

  구현 방법

 

 

// arr: 원본배열, left: 왼쪽 포인터, right: 오른쪽 포인터
function quickSort(arr, left = 0, right = arr.length - 1) {
	if(left <= right) {

    const pivotIndex = partition(arr, left, right);
    
	quickSort(arr, left, pivotIndex - 1)
    
	quickSort(arr, pivotIndex + 1, right)

  }
		
}


function partition(arr, left, right){

	// pivot: left(초기: 0), low: 왼쪽 포인터, high: 오른쪽 포인터
  const pivot = arr[left];
  let low = left + 1;
  let high = right;
  
	// low 와 high 가 교차할 때 까지 반복
  while(low <= high){
		
		// low 이동
    while(arr[low] < pivot) low++;
		// high 이동
    while(arr[high] > pivot) high--;

		// 두 포인터가 멈추었을 때 서로 교차하지 않았다면 서로변경
    if(low <= high){
      [arr[low], arr[high]] = [arr[high], arr[low]]
      low++;
      high--;
    }
  }

  // 두 포인터가 멈추었고 서로 교차하였을 때는 오른쪽 포인터와 pivot 을 변경
  [arr[left], arr[high]] = [arr[high], arr[left]]

  // 정렬된 pivot 은 high 의 자리에 있으므로 high 를 리턴
  return high
	
}
function isArraySorted(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
          return false;
      }
  }
  return true;
}

const arr = [26, 71, 93, 7, 42, 56, 8, 48, 11, 23, 93, 4, 25, 66, 53, 6, 67, 30, 33, 44, 42, 52, 99, 15, 64, 58, 49, 69, 61, 3, 56, 7, 3, 35, 35, 17, 32, 88, 95, 78, 5, 56, 6, 12, 15, 85, 55, 76, 81, 57, 70, 60, 25, 55, 6, 68, 19, 94, 29, 76, 35, 95, 98, 77, 31, 80, 1, 96, 99, 24, 90, 54, 12, 2, 7, 11, 88, 99, 67, 15, 59, 53, 98, 11, 39, 68, 52, 71, 38, 43, 18, 6, 18, 59, 10, 49, 36, 21, 5, 70]

quickSort(arr);

for(let i = 0; i < arr.length; i++){
  console.log(arr[i]);
}
console.log(`정렬 여부 확인: ${isArraySorted(arr)}`);