Quick Sort 퀵 소트 소개 (작동방식/ pivot 구하기/ 코드 구현/ 시간복잡도) : Programming Story

1. 퀵소트란?

퀵소트란 pivot (피벗)을 사용하여서 효과적으로 정렬할 수 있는 알고리즘이다. 피벗을 하나 고른 다음에 그것보다 작은 것은 앞으로 보내고, 그것보다 큰 것은 뒤로 보내는 식으로 작동한다. 그 이후에 피벗을 기준으로 왼쪽 오른쪽에서 각각 다시 퀵 소트를 실행한다.

quick sort는 평균적인 상황에서 O(nlogn)으로 최고의 성능을 보이는 알고리즘이다. 다만, 최악의 경우 시간복잡도 O(N^2)을 가질 수도 있다.

2. 퀵소트 과정

<예시>

Quick Sort를 활용해 정렬할 예시 배열

위와 같은 배열을 Quick Sort를 활용해 정렬한다고 하자. 그러면 우선 pivot을 정해야 한다. pivot을 정하는 것에는 다양한 방법이 있는데 오늘은 그냥 중앙을 pivot으로 정하자. (pivot을 어떻게 정해야 가장 효율적인지에 관한 이야기도 많지만 확실한 답은 없기 때문에)

1. pivot 정하기

pivot 정하기

그러면 위와 같이 3이 pivot이 된다. (0+3)/2이므로 1번 index가 중앙인 것이다.

2. pivot과 가장 마지막 index의 수 바꾸어주기

그러면 이후에 pivot 위치의 수와 가장 마지막 index 수를 바꾸어주어 pivot 수가 가장 오른쪽에 위치하도록 잠시 옮겨놓자

pivot 인 수를 가장 마지막 index로 옮기기

위 그림처럼 pivot이었던 3을 가장 오른쪽 index에 배치해두었다.

3. 각 수를 하나씩 검사하면서 pivot보다 작은 수는 앞쪽으로 옮김

이제 각 배열의 수를 하나씩 검사하면서 pivot보다 작은지를 판단한다. 여기서 실제 pivot은 가장 마지막 index에 있기 때문에 임시 pivot index의 역할을 해줄 수 있는 index를 하나 설정해준다 (tmp라고 하겠다). 만약 pivot보다 작다면 a[i] (지금 검사하고 있는 수)와 a[tmp]를 바꾸어주고 tmp를 하나 증가시켜준다.

1) 0번 index의 1 검사

4 검사

4은 pivot 수인 3보다 크기 때문에 tmp에 변동이 없고 a[0]과 a[tmp]를 바꾸어줄 필요도 없다. 따라서 다음 index를 검사할 때도 tmp의 위치는 유지된다.

2) 1번 index의 1 검사

1 검사

1은 pivot 수인 3보다 작기 때문에 a[1]과 a[tmp] 즉 4를 swap 해주어야 한다. 그리고 tmp도 1 증가시켜주어야 한다.

결과적으로 2) 단계를 수행하고 나면, 아래와 같이 변한다.

변경된 배열

3) 2번 index의 7검사

7은 pivot 수인 3보다 크기 때문에 tmp에 변동이 없고 a[tmp]와 a[2]를 변경해줄 필요도 없다.

4) 3번 index :

3번 index는 원래 pivot이기 때문에 이제 수행을 그만한다.

4. pivot의 수를 원래 자리로 옮겨놓기

다시 pivot의 자리를 원래 자리로 옮겨놓아야 한다. tmp가 가리키는 곳이 pivot 수가 있어야 할 자리임으로 a[tmp]와 a[pivot]을 변경해주면 된다.

pivot을 원자리에 위치시켜놓기

위와 같이 변경할 수 있다. 이렇게 한 싸이클을 마치고 나면 3이 index 1에 위치하게 된다. 이 뜻은 3이 있어야 할 자리는 1번 index라는 것을 알 수 있다. 하지만 pivot을 제외한 나머지 숫자들은 정렬이 되지 않은 상태이다. 우리는 단순히 pivot이 있어야 할 자리만 찾은 것 뿐이다.

5. pivot 전후의 숫자들 quickSort 다시 실행

pivot 만 제대로 된 위치를 찾았고 전후의 숫자들은 정렬이 되지 않은 것이므로 다시 quickSort를 재귀적으로 호출해서 실행해준다.

그러면 퀵 소트를 코드로 구현하면 어떻게 구현할 수 있을까?

함수를 여러개를 만들어서 효과적으로 구현해보도록 하겠다.

1. int find(int start, int end) : 시작 인덱스와 끝 인덱스에서 pivot의 위치를 찾아서 return 해주는 함수. pivot의 위치를 알려줄 뿐만 아니라 배열 안에서 수도 서로 swap 해주는 역할을 하는 함수

int find(int start, int end){
 int pivotindex=choose(start, end);
 int pivot=a[pivotindex]; //피봇 값
 swap(a[pivotindex], a[end]); //pivot을 임시적으로 가장 오른쪽으로 미루어둠
 int tmp=end; //임시 pivot index
 
 for(int i=start; i<end; i++){
  if (a[i]<pivot){
    swap(a[i], a[tmp]);
    tmp++;
  }
 }
 swap(a[tmp], a[end]); //다시 pivot 원상복구
 return tmp; //pivot index return
}

2. int choose (int start, int end) : pivot의 인덱스를 알려주는 함수 (여기서는 중앙 index로 구현) find 함수 안에서 한꺼번에 해도 되지만 코드의 가독성을 위해서 새로 함수를 하나 더 만들어주었다.

int choose (int start, int end){
 return (start+end)/2;
}

3. quicksort (int start, int end) : 1번 find에서 찾은 pivot의 index를 기준으로 (start부터 pivot-1)까지, (pivot부터 end까지) 재귀적으로 quickSort를 진행해주는 함수

void quickSort(int start, int end){
 if (start<end){
   int pivot=find(start, end); 
   quickSort(start, pivot-1);
   quickSort(pivot+1, end);
  }
}

이렇게 위의 세 함수를 만들어주면 그림에서 설명했던 quickSort의 작동원리를 코드로 구현할 수 있다.

3. QuickSort 시간복잡도

위에서도 언급했지만 퀵소트는 평균적인 상황에서 O(nlogn)으로 최고의 성능을 보이는 알고리즘이다. 하지만 최악의 상황에서는 O(N^2)라는 시간복잡도를 보일 수 있다. 이유는 pivot으로 선택한 것이 계속해서 배열의 첫 index에 위치할 수도 있기 때문이다. 다시 말해서 우리는 pivot을 기준으로 전, 후 배열을 다시 quickSort로 재귀적으로 정렬했는데 pivot의 위치가 계속해서 가장 처음으로 위치한다면 전, 후 배열을 sorting하지 않고 계속 pivot 이후의 배열만 sorting을 하게 된다. 그러면 모든 N개의 수에 대해서 계속 quickSort를 해야 하므로 O(N^2)라는 시간복잡도를 보이게 된다.