2016. 12. 9. 14:01

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


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



퀵정렬 (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) 이다.


감사합니다.



동영상 예시

출처 : 유투브동영상







Posted by 시리시안

댓글을 달아 주세요

2016. 12. 8. 11:43

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


이번 포스팅에선 순차탐색에 대하여 정리하겠습니다.


순차 탐색 (Linear Search)


사실 순차 탐색, Linear Search라고 이름이 거창하지만, 한번쯤은 누구나 다 해봤을 탐색법입니다.


맨 앞에서부터 맨 끝까지 순서대로 탐색을 하는 알고리즘입니다.


시간 복잡도는 당연히 O(n)을 가지고있습니다.


종료 조건


배열에 길이에서 숫자를 발견하거나, 끝까지 발견하지 못할 경우 종료됩니다.


예제 코드


1
2
3
4
5
6
7
8
9
10
int Algorithm(int[] arrays, int target)
{
 
    for(int i=0; i<arrays.Length; ++i)
    {
        if(arrays[i] == target)
            return i;
    }
    return -1;
}
cs


정말 간단했네요..


감사합니다.

Posted by 시리시안

댓글을 달아 주세요

2016. 12. 8. 10:46

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


이번 포스팅에선 이진 탐색 알고리즘에 대해서 적어보려고 합니다.


이진 탐색 알고리즘 (Binary Search)


이진 탐색 알고리즘을 하기 위해선 데이터가 정렬되어있어야 합니다. 


정렬된 데이터가 아니면 적용이 불가능한 알고리즘이기 때문이죠.


코드를 살펴보기 전에 알고리즘에 진행 방식을 보겠습니다.


배열 { 1, 3, 4, 5, 7, 8, 10, 20, 60, 100 } 에서 5를 찾아보겠습니다.


 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 


첫번째 케이스


배열 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눕니다. 그 인덱스에 해당하는 값이 5인지 확인하고 아니라면 5보다 큰지, 작은지 확인합니다.


 (0 (시작 인덱스) + 9 (마지막 인덱스)) / 2 = 4.5 (나머지는 버립니다.) => 4


array[4]는 7 이므로 값이 같지 않으니 대 소 를 비교합니다.


array[4]가 찾고자 하는 값(5)보다 크니 4~마지막 인덱스 까진 탐색에서 제외합니다.



 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 


두번째 케이스


(0 (시작 인덱스) + 3 (마지막 인덱스)) / 2 = 1.5 => 1


array[1] 는 3 이므로 값이 같지 않으니 대 소 를 비교합니다.


array[1]가 찾고자 하는 값(5)보다 작으니 시작인덱스 ~ 1 까지 탐색에서 제외합니다.


 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 



세번째 케이스


(2 (시작 인덱스) + 3 (마지막 인덱스)) /2 = 2.5 => 2


array[2]는 4이므로 값이 같지 않으니 대 소 를 비교합니다.


array[2]가 찾고자 하는 값(5)보다 작으니 시작인덱스~2까지 탐색에서 제외합니다.



 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 


네번째 케이스


(3 (시작 인덱스)  + 3 (마지막 인덱스)) /2 = 3


array[3]은 5이므로 찾고자 하는 값과 같으니 반환하며 탐색을 종료합니다.



위처럼 절반 씩 줄어 들면서 값을 검색하니, 시간 복잡도는 O(Log N)을 가집니다.


값을 못찾았다면, 시작인덱스가 마지막인덱스 보다 커진 경우 탐색을 종료하며 실패를 반환합니다.



예시 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int searchint(int[] intarrays, int index)
{
    int from = 0;
    int to = intarrays.Length - 1;
 
    while (from <= to)
    {
        int mid = (from + to) / 2;
 
        if (intarrays[mid] > index) 
        {
            to = mid - 1;
        }
        else if (intarrays[mid] < index)
        {
            from = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
cs



알고리즘의 종료 조건


위 코드처럼 시작인덱스(from)이 마지막인덱스(to)보다 커지면 종료합니다.

Posted by 시리시안

댓글을 달아 주세요

2016. 12. 7. 17:28

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


이번 포스팅에선 피보나치 수열에 대하여 정리 해보려고합니다.


피보나치 수열


피보나치 수열은 앞의 두 수 를 더해서 현재 위치의 수를 만드는 수열을 말합니다.


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...


시작 두 수 인 0, 1을 제외하고 3번째 수부터 바로 전 수 와 전 전 수의 합계를 나타내면 됩니다.


0, 1, (0+1) , ((0+1) + 1) , (((0+1) + 1) +(0+1)) ...


간단한 알고리즘이라서 그런지 구현 방법은 여러가지가 있습니다.


먼저 재귀함수 호출을 이용한 피보나치 수열 구현 입니다.


1
2
3
4
5
6
7
8
int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Algorithm(n - 1+ Algorithm(n - 2);
}
cs


1번째와 2번째의 값은 0과 1로 정해져있으니, 각각 0과 1을 반환하고, n의 전 값과, n의 전전 값을 더해서 리턴하는 형식을 가지고 있습니다.


간단하게 구현을 완료했지만, Algorithm 함수를 들어갈때마다 계속 n이 1인지, 2인지를 검사 하고 시작해야 하네요.


반복전인 2회 검사를 제거 하기 위해 이번엔 반복문으로 구현해봤습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
    {
        int beforevalue = 0;
        int current = 1;
 
        for(int i=1; i<n; ++i)
        {
            int temp = current;
            current += beforevalue;
            beforevalue = temp;
        }
        return current;
    }
}
cs


간단하게 재귀 함수를 호출하는 부분을 for문으로 변경해봤습니다.


current는 현재 숫자, beforevalue는 이전 숫자입니다.

다음 숫자는 현재 숫자 + 이전숫자 이므로, current와 beforevalue를 더해서 구합니다.


이것 외에 다른 방법은.. 성능상으로는 비슷하지만 코드상으로는 다른 '꼬리 재귀 함수'를 이용한 구현법이 있습니다.


1
2
3
4
5
6
7
8
9
10
int Algorithm(int n){
    return AlgorithmTail(n, 01);
}
 
int AlgorithmTail(int n, int before, int next){
    if (n == 0)
        return before;
    else
        return AlgorithmTail(n - 1, next, before + next);
}
cs


구하려는 n번째 자리수를 이용하여 n을 한단계씩 줄여가며 before와 next를 더해가는겁니다. 


한 타임이 지나면

before는 next가 되며

next는 before + next가 됩니다.


그렇게 반복되며 꼬리재귀함수를 돌다가 n값이 0 이라면 현재 값(before)를 반환합니다.


꼬리 재귀 함수에 관해선 다른 포스팅에서 자세히 다루도록 하겠습니다.



감사합니다.



Posted by 시리시안

댓글을 달아 주세요