Quick sort(퀵 정렬)/C,C++

 

Quick sort ( 퀵 정렬 )

 

가장 빠른 정렬 알고리즘 중 하나로 빠른 정렬 속도 덕에 널리 쓰입니다.

 

 

C/C++ 코드 

void quick_sort(int a[], int left, int right) {
 
    int pl = left;
    int pr = right;
    int x = a[(pl+pr)/2];
 
    do {
        while(a[pl] < x) pl++;
        while(a[pr] > x) pr--;
 
        if (pl<=pr){
            swap(int,a[pl],a[pr]);
            pl++;
            pr--;
        }
 
    }while(pl<=pr);
 
    if(left < pr) quick_sort(a,left,pr);
    if(pl < right) quick_sort(a,pl,right);
}
 

 

퀵 정렬의 구현

 

퀵 정렬을 구현하기 위해서는 커서 2개와 그룹을 나누는 기준인 '피벗(pivot)'이 필요합니다.

 

커서 두 개중 하나는 정렬하려는 배열의 맨 앞을, 다른 하나는 배열의 맨 끝을 가리키고

 

피벗은 두 커서의 중앙값으로 정하고 시작합니다.

 

 

 

 

길이가 n인 정수형 배열 A이 있다고 했을 때

 

왼쪽 커서 : pl = 0;

오른쪽 커서 : pr = n-1;

피벗(pivot) : p = a [ (pl+pr) / 2] 

 

피벗(pivot) :  p = 7 

 

 

 

 

 

퀵 정렬을 하기 위해서는 배열을 피벗 값 이하의 값을 가진 원소들의 모임과 이상의 값을 가진 모임,

두 그룹으로 나누는 작업을 반복해야 합니다.

 

 

 

 

 

 

나누는 작업은 아래와 같습니다.

 

 

1. 피벗 값보다 크거나 같은 요소를 찾을 때까지 왼쪽 커서 pl을 오른쪽으로 옮기고

 

2. 피벗값보다 작거나 같은 요소를 찾을 때까지 오른쪽 커서 pr을 왼쪽으로 옮긴 뒤

 

3. pl 이 가리키는 값과 pr 이 가리키는 값을 서로 교환하는 작업을

 

4. pl과 pr이 서로 교차할 때까지 해야 합니다.

 

 

 

 

 

 

배열 A로 하나씩 설명하자면,

 

 

1. 피벗 값보다 크거나 같은 요소를 찾을 때까지 pl을 오른쪽으로 옮기고

 

 

피벗 값이 7이므로 pl을 9까지 오른쪽으로 옮기고

 

 

 

2. 피벗 값보다 작거나 같은 요소를 찾을 때까지 pr을 왼쪽으로 옮긴 뒤

 

 

 

3.  pl 이 가리키는 값과 pr 이 가리키는 값을 서로 바꾸어주는 작업을

 

 

pl ,pr 교환

3

1

0

5

7

4

8

9

12

                             

 

 

4. pl과 pr이 서로 교차할 때까지 해야 합니다

 

                                

 

교환

3

1

0

5

4

7

8

9

12

                                                                 

 

 

      pl, pr 교차

                                                                     

 

 

발 그림 죄송합니다 ㅠㅠ

 

 

 

위 작업을 통해

 

피벗 값 이하의 원소들을 가진 모임과 (A [0]~A [4])

피벗 값 이상의 원소들을 가진 모임 (A [5]~A [8])

 

두 그룹으로 배열을 나눌 수 있습니다.

 

 

 

 

 

배열을 두 그룹으로 나누었지만 아직 정렬이 완성되지는 않았습니다.

 

나눈 두 그룹을 B, C 라 부르겠습니다.

 

3

1

0

5

4

7

8

9

12

|-----------------------  피벗(7) 이하 값  -----------------------------|

                                   그룹 B                                                |---------------  피벗(7) 이상 값  ---------------|

 

                                                                                                                     그룹 C

 

 

배열을 완전히 정렬시키려면 배열 A를 두 그룹으로 나누었듯이 나뉜 그룹을 피벗 값에 따라 나누는 작업을 반복하면 됩니다. 요소가 1개인 그룹은 나눌 필요가 없습니다.

 

 

 

 

즉, 새로운 그룹의 첫 인덱스를 left, 마지막 인덱스를 right이라고 한다면

 

pr이 left 보다 오른쪽에 있다면 왼쪽 그룹을 나누고 (left < pr)

pl이 right 보다 왼쪽에 있다면 오른쪽 그룹을 나누는 작업을(pl < right)

 

반복하면 됩니다.

 

                                               

 

 

0

1

3

5

4

7

8

9

12

                                                                             

                                   요소 1,2,3 교환                                                         교환 불필요                                                                          

 

0

1

3

4

5

7

8

9

12

 

요소 3, 4 교환

정렬 완료

 

 

코드) C++

 

 

void quick_sort(int a[], int left, int right) {
 
    int pl = left;
    int pr = right;
    int x = a[(pl+pr)/2];
 
    do {
        while(a[pl] < x) pl++;
        while(a[pr] > x) pr--;
 
        if(pl<=pr){
            swap(int,a[pl],a[pr]);
            pl++;
            pr--;
        }
 
    }while(pl<=pr);
 
    if(left < pr) quick_sort(a,left,pr);
    if(pl < right) quick_sort(a,pl,right);
}

 

 

• 퀵 정렬의 시간 복잡도

 퀵 정렬의 시간 복잡도는 O(n logn)으로 빠른 정렬 알고리즘에 속합니다.

하지만 피벗 선택에 따라서 시간 복잡도가 최악의 경우에는 O(n^2)가 되어버리는 경우가 있습니다.

이 때문에 최악의 시간 복잡도를 피하는 피벗 선택법 또한 존재합니다.

 

 

 

  최악의 시간 복잡도를 피하는 피벗 선택법

 

 

-> 첫 번째, 중앙, 마지막 원소를 정렬시킵니다. 

23

2

7

9

8

1

4

14

13

 

8

2

7

9

13

1

4

14

23

 

-> 중앙값을 피벗으로 선택합니다.

8

2

7

9

13

1

4

14

23

 

 

 

• 결론

빠른 정렬 속도로 정렬할 데이터가 많은 경우 효율적인 정렬 알고리즘입니다.

 

장점 : 정렬 속도가 매우 빠른 정렬 알고리즘

단점 : 구현이 조금 복잡하고, 피벗 선택에 따라서 시간 복잡도가 최악의 경우 O(n^2)이 됨