정렬 알고리즘 기초2 - 퀵 정렬(Quick Sort)

By on August 14, 2019

1. 퀵정렬 알고리즘(Quick Sort)

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
일반적인 상황에서 최고의 정렬 성능을 보인다. 프로그래밍에 가장 많이 구현된 정렬 알고리즘 중 하나이다.
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 정렬 순서는 아래와 같다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
- 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
정렬 순서
예1) 3,5,1,2,4,8,6,9,7 배열을 오름차순으로 정렬 하려고 할 경우
- pivot : 3으로 설정
3 5 1 2 4 8 6 9 7 ==> 3(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 5선택
3 5 1 2 4 8 6 9 7 <== 마지막에서 시작해서 왼쪽으로 진행하여 3(pivot)보다 작은 값을 찾는다. 2선택
〉 5와 2의 자리 교체

3 2 1 5 4 8 6 9 7 ==> 3(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 5선택
3 2 1 5 4 8 6 9 7 <== 마지막에서 시작해서 왼쪽으로 진행하여 3(pivot)보다 작은 값을 찾는다. 1선택
〉 중요 : 왼쪽의 진행 방향이 오른쪽의 진행방향과 엇갈렸을 경우에는 첫번째 값 3(pivot)을 가장 작은값(1) 과 자리를 교체한다.

1 2 3 5 4 8 6 9 7 ====> 이 과정에서 분할이 진행된다.
3(pivot)을 중심으로 3(pivot)보다 작은 집합 : {1, 2} ==> 왼쪽그룹(pivot = 1 로 설정)
3(pivot)을 중심으로 3(pivot)보다 큰 집합 : {5 4 8 6 9 7} ==> 오른쪽 그룹(pivot = 5 로 설정)

1 2 ==> 1(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 2선택
1 2 <== 마지막에서 시작해서 왼쪽으로 진행하여 1(pivot)보다 작은 값을 찾는다. 1선택(자기자신)
〉 중요 : 엇갈려서 자리를 교체 함(자기자신을 자신의 자리와 교체 하기 때문에 변화 없음) ==> 정렬 끝

5 4 8 6 9 7 ==> 5(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 8선택
5 4 8 6 9 7 <== 마지막에서 시작해서 왼쪽으로 진행하여 5(pivot)보다 작은 값을 찾는다. 4선택
〉 중요 : 엇갈렸기 때문에 5(pivot) 과 4의 자리를 교체 한다.
4 5 8 6 9 7 ====> 분할진행
5(pivot)을 중심으로 작은 수 집합 : {4} ==> 왼쪽 그룹(pivot = 4 로 설정)
5(pivot)을 중심으로 큰 수 집합 : {8, 6, 9, 7} ==> 오른쪽 그룹(pivot = 8 로 설정)

8 6 9 7 ==> 8(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 9선택
8 6 9 7 <== 마지막에서 시작해서 왼쪽으로 진행하여 8(pivot)보다 작은 값을 찾는다. 7선택
〉 9 와 7의 자리 교체

8 6 7 9 ==> 8(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 9선택
8 6 7 9 <== 마지막에서 시작해서 왼쪽으로 진행하여 8(pivot)보다 작은 값을 찾는다. 7선택
〉 중요 : 엇갈렸기 때문에 8(pivot) 과 7의 자리를 교체 한다. ==> 분할

7 6 ==> 7(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 없음
7 6 <== 마지막에서 시작해서 왼쪽으로 진행하여 7(pivot)보다 작은 값을 찾는다. 6선택
중요 : 엇갈렸기 때문에 7(pivot) 과 6의 자리를 교체 한다.

8 9 ==> 8(pivot)에서 시작해서 오른쪽으로 진행 하여 큰값을 찾는다. 9선택
8 9 <== 마지막에서 시작해서 왼쪽으로 진행하여 8(pivot)보다 작은 값을 찾는다. 없음.

〉 1 2 3 4 5 6 7 8 9 왼쪽 그룹과 오른쪽그룹 모두 정렬 완료.
시간 복잡도 : O(n * log n)
예) 10개의 배열이 주어 졌을 경우 피벗을 기준으로 반으로 분할 하여 정렬 하게 되므로 50번만으로 정렬이 완료 되게 된다.
(10 / 2) * 5 = 25
(10 / 2) * 5 = 25
참고 : Arrays.sort() 메소드내부에 구현되어있는 DualPivotQuickSort.class 에서도 퀵정렬을 이용하여 정렬 하도록 구현 되어있다.
퀵정렬 알고리즘 애니메이션

퀵 정렬 알고리즘 자바 소스

public class QuickSort {
  private static int[] numbers = { 3, 5, 1, 2, 4, 8, 6, 9, 7 };
  public static void main(String[] args) {
      quickSort(numbers, 0, numbers.length-1);
      System.out.println(Arrays.toString(numbers));
  }
	
  public static void quickSort(int[] numbers, int left, int right) {
      int start, end, pivot, tmp;
        
      if(left >= right) { // 원소가 1개일 경우
          return;
      }
        
      start = left;
      end = right;
      pivot = numbers[(left+right)/2];
      //분할 과정
      while (start < end) {	//엇갈렸을 경우
            
          while (numbers[start] < pivot) start++;    //피벗 값 보다 큰 값을 만날때까지 반복
            
          // 이 부분에서 arr[end-1]에 접근해서 익셉션 발생가능하기 때문에 end > start 조건 필요
          while (numbers[end] > pivot && end > start) end--;    //피벗 값 보다 작은 값을 만날때까지 반복

          tmp = numbers[start];
          numbers[start] = numbers[end];
          numbers[end] = tmp;
      }
      //정렬 과정
      quickSort(numbers, left, start - 1);
      quickSort(numbers, end + 1, right);
  }
}

추가 팁 : 퀵정렬은 최악의 경우 O(n²) 이 될 수 있다.
예) 1 2 3 4 5 6 7 8 9 를 정렬 해야 할 경우
1 2 3 4 5 6 7 8 9 ==> 1(pivot) 에서 시작해서 큰 수 2를 찾음
1 2 3 4 5 6 7 8 9 <== 마지막에서 시작해서 작은 수 1을 찾음.
＞ 엇갈림 : 자기 자신을 작은수인 자기 자신과 교체

1 2 3 4 5 6 7 8 9 ==> 2(pivot) 에서 시작해서 큰 수 3를 찾음
1 2 3 4 5 6 7 8 9 <== 마지막에서 시작해서 작은 수 2를 찾음.
＞ 엇갈림 : 자기 자신을 작은수인 자기 자신과 교체

이처럼 정렬이 되어있는 배열의 경우 1번의 반복에 1개의 숫자를 정렬 하기 때문에 O(n²) 의 성능을 보인다.
이런 경우는 삽입정렬이 매우 빠르게 정렬 할 수 있다.