TIL : Today I Learned

# 퀵 정렬

  • 퀵 정렬은 분할 정복 알고리즘이다.
  • 분할을 하는데, 정확히 반을 가르지 않고 정해진 피벗으로 가른다.
  • 최악의 경우 O(n^2)의 시간복잡도를 갖는다.
  • 보통 일반적으로 O(nlogn)이 된다.

# 분할과 정복?

여기서 의미하는 분할과 정복은 데이터가 들어있는 배열 혹은 리스트를 쪼개고(분할) 그리고 그 쪼갠 리스트를 정렬(정복)하며 다시 묶어주는 것을 의미한다.
퀵정렬의 경우 pivot을 기준으로 정렬을 하며 분할을 수행함.

# 구현 방법

  1. pivot을 정해준다.(분할할 지점)
  2. pivot을 기준으로 왼쪽은 작은거 오른쪽은 큰게 오도록 설정한다.(pivot보다, 오름차순 정렬시)
  3. 피벗을 적절한 위치로 옮겨준다.
  4. 피벗 기준 양 옆의 분할된 배열에 1번부터 3번을 반복 시행한다.(모든 값을 다 쪼갤 때 까지)
public int partition(int[] array, int left, int right) {
    int pivot = array[left]; 
    int i = left, j = right;
    
    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    
    return i;
}

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
     
    int pivot = partition(); 
  
    quickSort(array, left, pivot-1);  
    quickSort(array, pivot+1, right); 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 퀵정렬의 특징

  • 시간복잡도는 O(nlogn) -> 데이터가 한번 분할될 때마다 모두 n개의 데이터를 확인해서 적절 위치에 넣고 logn으로 분할 되기 때문에
  • 시간복잡도가 최악의 경우 O(n^2)이 될 수 있음. -> 정해진 피벗이 항상 왼쪽이나 오른쪽으로만 붙어있을 때
  • 빠르고 자신의 배열 한 곳에서만 처리하므로 메모리의 낭비가 없음.
  • 분할이 어찌 되느냐가 성능에 대한 주요 포인트임(피벗을 어떻게 잡을지를 잘 결정해주면 해결 가능)

← Key →