'퀵'에 해당되는 글 1건

  1. 2016.12.09 [Algorithm] 퀵 정렬(Quick Sort)에 대해 알아보자!
2016. 12. 9. 14:01

[Algorithm] 퀵 정렬(Quick Sort)에 대해 알아보자!

프로그래밍/Algorithm

안녕하세요. 게임개발자 놀이터 입니다.


이번 포스팅에선 퀵 정렬에 대해 정리해보려고 해요.



퀵정렬 (Quick Sort)


퀵정렬은 '찰스 앤터니 리처드 호어(1962)'가 개발한 정렬 알고리즘 이라고 합니다.


퀵 정렬은 기준(pivot)을 선택하여 기준보다 작은 데이터를 왼쪽에 위치시키고, 큰 데이터는 오른쪽에 위치시킵니다.

이 과정이 끝나면 기준(pivot)이 된 요소는 정렬된 위치를 찾습니다. 결과적으로 기준보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽에 위치하게됩니다. 이러한 알고리즘을 pivot을 기준으로 왼쪽 데이터 그룹과 오른쪽 데이터 그룹에 재귀적으로 더이상 불가능 할때까지 반복합니다. (데이터 그룹의 갯수가 0 이거나 1개일때까지 반복)

반복이 종료되면 정렬된 데이터 그룹을 얻을 수 있습니다.


(출처 : 위키백과 퀵정렬)


정렬과정



임의의 데이터 배열을 가지고 정렬 해보겠습니다.

15 13 9 10 26 24 85


1. 먼저 Pivot을 설정합니다.

15 13 9 10 26 24 85


2. Pivot(15)를 기준으로 보다 작으면 왼쪽, 크면 오른쪽에 위치시켜 분할합니다

13 9 03 15 26 24 85


3. 좌 우 로 분할된 데이터로 다시 (1,2)의 과정을 실행합니다.


( 13 9 10 )   15   ( 26 24 85 )

( 13 9 10 )   15   ( 26 24 85 )

( 9 10 13 )   15   ( 26 24 85 )

( 9 10 )   13 15   ( 26 24 85 )


9 10 13 15   ( 26 24 85 )

9 10 13 15   ( 26 24 85 )
9 10 13 15   ( 24 26 85 )


9 10 13 15 24 26 85


정렬 완성!


예제 코드


2개의 함수와 재귀함수를 이용한 방법

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void QuickSort(int arrays[], int left, int right)
{
    if(left<right)
    {
        int pivot = Partition(arrays,left,right);
        QuickSort(arrays, left, pivot-1);
        QuickSort(arrays, pivot+1, right);
    }
}
 
int Partition(int arrays[],int left, int right)
{
    int pivot = left;
    right = right +1;
 
    while(left<right)
    {
        do
        {
            ++left;
        }while(arrays[left] < arrays[pivot]);
 
        do
        {
            --right;
        }while(arrays[right] > arrays[pivot]);
 
        if(left<right)
        {
            int swap = arrays[left];
            arrays[left] = arrays[right];
            arrays[right] = swap;
        }
    }
 
    int swap = arrays[pivot];
    arrays[pivot] = arrays[right];
    arrays[right] = swap;
 
    return right;
}
cs


1개의 재귀 함수를 이용한 방법


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
void QuickSort(int arrays[], int left, int right)
{
    int row = left;
    int high = right;
    int pivot = arrays[(left + right) / 2];
 
    while (row <= high) {
        while (arrays[row] < pivot)
            row++;
        while (arrays[high] > pivot)
            high--;
 
        if (row <= high) {
            int tmp = arrays[row];
            arrays[row] = arrays[high];
            arrays[high] = tmp;
            row++;
            high--;
        }
    };
 
    if (left < high)
        QuickSort(arrays, left, high);
 
    if (row < right)
        QuickSort(arrays, row, right);
}
cs




알고리즘 분석



가장 평균의 상황에서의 시간복잡도가 알고리즘의 시간 복잡도라고 할 수 있다.


크게 2가지 상황을 추축할수있다.


1. 최고의 경우, 나누어지는 족족 마다 반씩 분할되는 경우.

2. 최악의 경우, 나누어지는 족족마다 1개와 나머지로 분할되는 경우.


우선 1번의 경우를 계산하면. 


횟수 = (2ⁿ - 1) + 2 x (2ⁿ-¹ - 1) ...

= ⁿ-¹Σ 2... 이거 수식을 어떻게 적어야 할지 모르겠다..


계산하면.. NLogN이 나온다.


2번의 경우는 N² 이 나온다.


나중에 수식을 제대로 추가할수있는 방법을 알게된다면.. 그때 수정 해야겠다.



쨋든 2번의 경우는 극단적인 상황이므로, 시간 복잡도는 1번의 경우를 사용해서 O(N logN) 이다.


감사합니다.



동영상 예시

출처 : 유투브동영상







저작자표시 비영리 변경금지

'프로그래밍 > Algorithm' 카테고리의 다른 글

[Algorithm] 선택 정렬에 대하여! (Insertion Sort)  (0) 2016.12.08
[Algorithm] 삽입 정렬에 대하여!( Insertion Sort )  (0) 2016.12.08
[Algorithm] 버블 정렬 이란? (Bubble Sort)  (0) 2016.12.08
[Algorithm] 순차 탐색 알고리즘에 대하여 (Linear Search)  (0) 2016.12.08
[Algorithm] 이진탐색 알고리즘에 대하여! (Binary Search)  (0) 2016.12.08
Posted by 시리시안

티스토리툴바