[알고리즘] Quick Sort

🧐 접근 방식

Quick Sort는 분할정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.

분할정복(divide and conquer)이란?
문제를 작은 2개의 문제로 분리해 해결한 후 결과를 모아 원래 문제를 해결하는 방법

🧑‍💻 구현 방식

1. 배열 가운데에서 하나의 원소 선택한다.(pivot)
2. 피벗 앞에는 피벗보다 값이 작은 원소들이 오고, 뒤에는 큰 원소들이 오도록 배열을 쪼갠다.(divide)
3. 분할된 두 개의 작은 배열에 대해 재귀적(Recursion)으로 이 과정을 반복한다.

• 재귀가 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해진다!

💻 예시 코드

public void quickSort(int[] arr, int left, int right) {
	if(left >= right) return;
    
    int pivot = partition(); // 분할
    
    quickSort(arr, left, pivot-1); // 정복(conquer)
    quickSort(arr, pivot+1, right); // 정복(conquer)
}

public int partition(int[] arr, int left, int right) {
	int pivot = arr[left]; // 가장 왼쪽값을 피벗으로 설정
    int i = left, j = right;
    
    while(i > j) {
      while(pivot < arr[j]) {
          j--;
      }
      while(i < j && pivot >=arr[i]) {
      	i++;
      }
      swap(arr, i, j);
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    
    return i;
}

⏳ 시간복잡도

• 최선의 경우 O(nlog₂n)
• 최악의 경우 O(n^2)

🎈 장단점

• 장점
  -불필요한 데이터 이동을 줄임
  -정렬하고자 하는 배열 안에서의 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않음
• 단점
  -불안정 정렬(Unstable Sort)
  -정렬된 배열은 오히려 Quick Sort의 불균형 분할에 의해 수행시간이 오래걸린다.

위 글은 아래 링크를 참고하여 작성되었습니다.
https://gyoogle.dev/blog/