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

📝 퀵 정렬(Quick Sort)

• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 알고리즘이다.
• 분할 정복 방식을 사용한다.
  • 분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
• 배열을 비균등하게 분할한다.

📝 개념(오름차순)

• 주어진 배열 내에서 하나의 원소(pivot)을 고른다.
• pivot을 기준으로 앞에는 pivot보다 값이 작은 모든 원소들을 오게 하고, 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 pivot을 기준으로 배열을 둘로 나눈다(분할).
• 분할을 마친 후 pivot은 움직이지 않는다.
• 분할 된 배열에 대해 재귀적으로 위와 같은 과정을 반복한다.
• 마지막으로 분할된 모든 값들을 합치면 정렬된 배열을 구할 수 있다.

💾 Java코드

private static void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int pivot = arr[left];
        while (l <= r) {
          	while (arr[l] < pivot){					//1️⃣
            		l++;
                }
          	while (pivot < arr[r]) {				//2️⃣
            		r--;
            	}

          	if (l <= r) {
                	if (l != r) {					//3️⃣
                   	  int tmp = arr[l];
                    	  arr[l] = arr[r];
                    	  arr[r] = tmp;
                	}
                l++;
                r--;
            }
        }
        if (left < r) quickSort(arr, left, r);				//4️⃣
        if (l < right) quickSort(arr, l, right);
    }

1. ① pivot의 왼쪽에는 pivot보다 작은 원소들이 위치하며, 큰 원소가 있다면 while문을 빠져나온다.
2. ② pivot의 오른쪽에는 pivot보다 큰 원소들이 위치하며, 작은 원소가 있다면 while문을 빠져나온다.
3. ③ l과 r이 역전되지 않으며 같지 않을 시에 두 원소의 위치를 바꾸어준다.
4. ④ l과 r이 역전된 후 pivot의 왼쪽과 오른쪽에 정렬되지 않은 부분을 퀵정렬 해준다.

📝 특징

• 장점

  • 속도가 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.

• 단점

  • 정렬된 리스트에 대해서 퀵 정렬의 불균형 분할에 의해 오히려 시간이 더 걸린다.
  • 불안정 정렬이다.

📝 시간 복잡도

최선의 경우 : O(N logN)
최악의 경우 : O(N^2)

📝 공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.