Hee's Blog

친절한 설명이 있는 좋은 글을 봐서 주인장 허락(?)을 구하고 퍼왔다.

출저는 미리 밝혀둔다.

[http://sirini.net/grboard2/blog/view/741]

좋은 자료가 많은 것 같아 종종 들러야 겠다.

긴긴 수를 구하는 알고리즘이며, 공부하여 내것으로 만들어야겠다.

아래는 글의 내용이다.

이번에는 아주 기본적인 것을 한 번 고찰해 보겠습니다.
이름하야, 긴 자리수 (혹은 무한 자리수!) 덧셈 뺄셈!! ...입니다. ^^;
굳이 설명이 필요할 것 같지는 않지만, 그래도 한 번 같이 생각해보자는 취지로
배경지식을 이야기 해 보도록 하겠습니다.

C 언어에서 기본적으로 제공하는 데이터 타입 중에
95782023975478592927348 이라는 숫자를 한 번에 담을 수 있는
타입이 무엇일까요? 네, 짱돌 날라오는 군요. ==3=3 (튀엇!!)

없죠.
어이 없어 하시는 것도 충분히 이해가 됩니다.
사실 저는 그 동안 이른 바, 강타입(strong type) 언어를 자주 쓰지 않아서
이런 부분에 특히 무신경 했습니다. 놀랍게도 Python 과 같은 언어에서는
아예 언어 특성상 이런 무한자리수 연산이 가능하도록 설계가 되어 있으니
더더욱 무신경했는지도 모릅니다. (반성중... ㅠ.ㅠ)

어쨌든, 현실세계는 냉정합니다.
95782... 로 시작하는 저런 긴 숫자는 최소한 C언어에서는 감당할 수가 없습니다.
반드시 배열이나 기타 다른 데이터 구조에 담아서 별도의 가공을 거쳐야 하지요.
슬픈 현실 앞에 비통한 마음 금할 길 없지만, 뭐 그래도 어쩌겠습니까.
언어에서 지원하지 않는다면 우회하는 길이라도 만들어 봐야지요. ^^;;

그래서 준비된 것이 이번에 소개해 드릴 긴 자리수 연산 알고리즘입니다.
원리는 단순합니다. 긴 자리수를 4자리 정수를 담을 수 있는 short 배열에다가
담습니다. 그리고 그 4자리씩 덧셈과 뺄셈을 해서 각각 자리올림수와 자리내림수를
처리해 줍니다. 그러니까 다시 말해 긴 자리의 숫자를 한 번에 처리하지 않고
4자리씩 끊어서 결국 4자리 short int 형 정수의 덧셈과 뺄셈을 하는 것입니다.

우선 아래 성공했을 시 나타날 화면을 보시겠습니다. (찬조출현: GNOME 콘솔)


(출력부분을 보시면 일부로 4자리씩 끊어서 나타난 것을 알 수 있습니다.)

이 전략을 좀 더 고급(?)스럽게 이야기하면 '분할 정복 전략' 이 되겠습니다.
즉, 한 번에 해결할 수 없는 단위의 큰 문제는 한 번에 해결할 수 있는 작은 몇 개의 문제로
나눠서 개별적으로 각개 격파 하는 것입니다. 위에서도 긴 자리수의 숫자를
short int 형으로 담아서 결국에는 4자리수 덧셈 / 뺄셈을 하도록 했습니다.

물론 여기서 만족할 수는 없겠지요.
아래 제가 작성한 코드의 문제점은 외부에서 입력을 받을 때 어떻게 할 것인가 하는 대비가
없다는 점입니다. 또한 수치를 반드시 short int 형 배열에 쪼개서 넣는 게 좋은지,
아니면 다른 타입으로 변환해서 넣는게 더 좋은지에 대해서도 고려를 해보아야 합니다.
더 깊게 생각해 본다면 CPU I/O 카운팅을 통해서 그야말로 마니악한 집요성으로
코드 최적화를 해 볼 수도 있겠습니다.

#include <stdio.h>

/* 이 소스코드는 기존 C 언어에서 지원하지 않는
무한자리수 산수 연산을 예시한다. 기본 데이터타입의 범위를 초과한
데이터의 덧셈과 뺄셈을 처리한다. */

#define LIMIT 32 /* 일단 여기서는 편의상 32자리 수로 제한한다. */
#define NUM ( ((LIMIT-1) / 4) + 1 ) /* 배열 크기다. short 타입의 배열을 쓴다. */

void iAdd(short*, short*, short*); /* 덧셈 */
void iSub(short*, short*, short*); /* 뺄셈 */
void iResult(short*); /* 결과 출력용 */

int main(int args)
{
    // 임의로 큰 수를 4자리로 short 배열에 담아두었다.
    // 실제 활용시에는 이 부분도 자동으로 되겠금 처리하는 게 좋다.
    static short a[NUM+2] = {1522,7849,2969,5432,1562,5092,8504,9562},
            b[NUM+2] = { 592,1949,6040,2947,6029,1156,5892,6782},
            c[NUM+2];
    
    printf("연산대상 A: 1522,7849,2969,5432,1562,5092,8504,9562￦n");
    printf("연산대상 B:  592,1949,6040,2947,6029,1156,5892,6782￦n");
    printf("---------------------------------------------------￦n");
    
    iAdd(a, b, c);
    printf("덧셈결과 +: ");
    iResult(c);
    
    iSub(a, b, c);
    printf("뺄셈결과 -: ");
    iResult(c);
    
    return 0;
}

// 긴 자리 덧셈하기
void iAdd(short a[], short b[], short c[])
{
    short i, cy=0;
    
    // 배열의 뒷자리부터 (그러니까 작은 단위수부터) 한 인덱스씩 계산한다.
    // 한 블럭의 덧셈결과가 10000 을 넘게 되면 자리올림수 처리를 해준다. (cy)
    for (i=NUM-1; i>=0; i--) {
        c[i] = a[i] + b[i] + cy;
        
        // 4자리수끼리 덧셈을 했는데도 10000 을 못넘겼으면 자리올림수는 없다!
        if(c[i] < 10000)
            cy = 0;
        else {
            c[i] = c[i] - 10000;
            cy = 1; // 덧셈해서 10000 을 넘겼다면 자리올림수를 만든다.
            // 위에서 만들어진 자리올림수는 그대로 다음 루프문에서 반영된다.
        }
    }
}

// 긴 자리수 뺄셈하기
void iSub(short a[], short b[], short c[])
{
    short i, br=0;
    
    // 역시 배열의 뒷자리 블럭부터 4자리씩 끊어서 계산한다.
    for (i=NUM-1; i>=0; i--) {
        c[i] = a[i] - b[i] - br;
        
        // 4자리수 뺄셈해서 결과가 0 이거나 혹은 0보다 크면 자리내림수는 없다!
        if (c[i] >= 0)
            br = 0;
        else {
            c[i] = c[i] + 10000; // 0보다 작게 되었다면 10000 을 빌리고
            br = 1; // 대신 그 윗자리수에서 1을 뺀다. 등가교환법칙
        }
    }
}

// 출력용
void iResult(short c[])
{
    short i;
    
    // 저장된 배열을 역시 4자리씩 끊어서 보여준다.
    for (i=0; i<NUM; i++)
        printf("%04d ", c[i]);
    printf("￦n");
}
알록달록한 코드 첫머리를 보고자 하실 분들을 위해... (찬조출연: GEdit)



개인적으로 파이썬에서는 어떻게 이런 긴자리수 연산을 지원하는지
무척 궁금합니다. 귀도 아저씨가 어떤 기가 막힌 알고리즘을 썼을지... ^^;;

에, 오늘은 좀 싱거웠나요?
사실 저는 이 부분 보면서 '아...! 이렇게 하면 되네...!' ...라는 둥,
뻘 소리를 남발했거든요. -_;;; (저는 처음에 한자리씩 차근차근 움직이면서
덧셈하고 자리올림수 만들고 다시 덧셈하고... 이런 걸 구상했었거든요. ㅠ.ㅠ)

참고로 긴 자리수 곱셈과 나눗셈 역시 여러분들께서 예측하신대로,
4자리수 씩 나눠서 쉽게 할 수 있습니다.
다만 곱셈의 경우는 4자리수씩 곱셈을 하고, 5번째 이상 숫자는 그 앞 블럭의
곱셈결과에 더해주는 과정을 처리해야 합니다. 그러니까 자리올림수가 한 개가
아니고 두 개가 있는 거지요. (직접 한 번 해 보아요~)

나눗셈의 경우는 좀 더 손을 가해야 합니다.
4자리수씩 하는 건 맞는데 4자리 나눗셈을 하고 나서 몫은 그대로 결과에 반영하고,
나머지는 10000배 해서 그 다음 블럭에 더한 후 다시 나누기를 해야 합니다.
그리고 계산 방향도 기존과는 반대방향이구요. (역시 직접 한 번 해 보아요~)

이 긴 자리수 사칙연산은 실제로도 굉장히 유용합니다.
어째서 유용한지, 내일 보여드릴 원주율(pi) 값 구하기편에서 같이 알아보도록 합시다.
(긴 자리수 나누기 함수도 사용합니다. 그리고 pi 값은 소수점 이하 1000 자리까지
슈퍼컴퓨터 뺨치고 달랠 수 있을 정도로 정확하게 구할 수 있습니다. ^^)

개인 프로젝트를 진행하다가 원을 그려야할 일이 생겨서 삼각함수를 이용하였다. 

후에 누군가에게 도움이 될 수 있으면 좋겠다는 생각으로 한번 정리해본다.

설명

원을 그리고 싶다는 것은 위 그림에서 θ가 0일때부터 360일때 까지의 점 p를 알고 싶다는 말과 같다.

각 앵글값일때의 점p는 위에서 나온 공식

sin(θ) = y / d   ==  y = sin(θ) * d  

cos(θ) = x / d   ==  x = cos(θ) * d

으로 구할 수있다.

다만 구해진 원은 d값을 반지름으로 하는 원일 것이다. 

또 C++에서 구현할때에는 앵글값을 0 ~ 360 까지 사용하는 것이 아니라 라디안으로 변환한 값을 사용해야한다.

코드는 아래와 같다.

Arrive는 찾기와 동일한 로직을 사용한다.

다른점이라 한다면 목표지점에 도착할 때 속도를 감속시켜 멈추는 로직이 추가된다는 것이다.

감속을 위한 계산법으로는 이미 사용하고 있는 Speed 값을 거리로 나누는 방법을 사용하였다.

공식은 다음과 같다.

Speed = Dist / ( Deceleration * 0.3 ) ( 거리 / (감속정도 * 0.3) )
DeceleratedVelocity = TargetVelocity * Speed / Dist  ( 감속된속력 = 원하는속력 * 속도 / 거리 )

위의 공식으로 생각해보면 속도와 거리가 줄어들수록 감속된 속력을 얻을 수 있다. 

원리는 거리가 줄어들면 Speed가 줄어들고 Speed와 거리가 줄어들면 결국 멈추도록 계산된다.

이렇게 얻은 감속된 속력에서 현재속도를 빼면 찾기때와 마찬가지로 조종힘 (D)을 얻을 수 있다. 

D = DV - C

코드

+ 후에 동영상을 올릴 수 있으면 추가하겠다.

Flee는 Seek의 반대성격을 가진다.

즉 찾기의 반대인 달아나기이다.

찾기가 에이전트를 목표하는 위치로 향하게 하는 조종힘을 만들어 냈다면

반대로 달아나기는 목표에서 멀어지는 조종힘을 만들어 내면 될 것이다.

원리는 아래와 같다.

찾기 때와 유일한 차이점은 원하는 속도(T)를 찾기에서는 Goal - Pos를 통하여 구했다는점과 달아나기에서는 Pos - Goal을 통해 구했다는 점이다.

찾기때와 마찬가지로 점차적으로 회전하도록 하기 위해 조종힘(D)을 구한다. D = T - C

코드는 아래와 같다.

코드

+ 후에 동영상을 올릴 수 있으면 추가하겠다.

이전 포스트를 이어서 퀵정렬의 pivot을 설정하는 방법에 대해 이야기 하도록 하겠다.

먼저 퀵정렬이 빠른 이유에 대해 알아야 한다.

전제 조건은 랜덤하게 정렬된 배열을 퀵정렬 알고리즘으로 정렬하는 것으로 한다.

퀵정렬의 구동 원리를 자세히 생각해보면 퀵정렬이 빠른 이유를 알 수 있다.

구동원리는 다음과 같다.

1. 피벗을 설정한다.

2. 피벗보다 큰 수는 오른쪽 작은 수는 왼쪽에 배치한다. 

3. 피벗을 기준으로 두개의 배열로 나눈다.

4. 각각의 배열을 1번부터 재귀적으로 반복한다.

만약 위의 방법만으로 정렬이 되는 것을 믿지 못하겠다면 [ 10. QuickSort ] 포스트를 참조하여 직접 따라가면서 컴파일 해보는 것을 추천한다.

힌트를 주자면 위의 단계처럼 두개의 배열로 나누다 보면 언젠가 하나의 배열이 3개 혹은 2개 혹은 1개가 되는데  

상식적으로 생각해보면 3개중 하나의 요소를 기준으로 좌우로 정렬한다면 오름차순으로 정렬될 수 밖에 없다는 것을 생각해보기 바란다.

다시 돌아와서 내가 생각한 퀵정렬이 빠른 가장 큰 이유는 바로 먼 거리 처리 능력 이다.

다음과 같은 두개의 배열을 두 가지 방법으로 정렬한다고 가정하자.

[2,  3,  4,  5,  6,  7,  8,  …  N,  1] => 1과 N, 1과 (N - 1), 1과 (N - 2), 1과 (N - 3), ... 1과 (N - (N - 1)) 비교 후 제자리를 찾음 (총 N - 1번 비교) 

[2,  3,  4,  5,  6,  7,  8,  …  N,  1] => 1과 2를 비교 후 작다면 1앞에 배치 (1번 비교) 

( 극단적인 상황이지만 먼거리 처리 능력을 보여주는 좋은 예 인것 같다. )

정렬 알고리즘의 수행시간을 결정짓는 모든 근원은 비교연산의 횟수와 교환연산의 횟수이다. 

그리고 똑같은 코드를 얼마나 반복하는지이다.

(상식적으로 for문을 아무런 처리 없이 n^2 번 반복시킨다고 해도 그렇게 오랜시간이 걸리지 않는다.)

결국 빠른 알고리즘은 코드를 얼마나 적게 수행하는 지에 따라 결정된다. 

코드를 적게 수행하는 방법은 비교연산을 통해 코드를 스킵하는 것이다.

이 모든 것이 비교를 하는 방법에 따라 결정되며 곧 먼거리를 한번에 이동할 수 있는 알고리즘이냐 아니냐의 문제라고 생각한다.

기존 알고리즘의 문제점

그렇다면 퀵정렬의 먼거리 처리능력이 소용없어지게 된다면 퀵정렬이 느려질까? 

퀵정렬의 먼거리 처리 능력을 없애는 방법은 이미 정렬된 배열을 정렬 시키거나 역순으로 정렬된 배열을 정렬시키는 것이다.

위 두가지의 경우 퀵정렬 역시 순차적으로 모두 비교를 하게 되기 때문이다.

그 이유는 앞서 구현하였던 퀵정렬이 피봇을 선택하는 방법에서 찾을 수 있다. 

무조건 left의 값을 피봇으로 설정 하기 때문에 피봇이 항상 가장 크거나 가장 작은 값이된다.

때문에 모든 요소와 비교를 하며 먼거리 처리능력도 소용이 없게 된다.

실제로 앞선 [ 10. QuickSort ]의 알고리즘으로 역순 배열이나 정렬된 배열을 정렬하면 n^2의 시간이 걸린다.

해결방안

어떻게 하면 퀵정렬이 랜덤인 상황이 아니더라도 빠른속도를 유지 할 수 있을까?

사실 이부분에서 나는 굉장히 많은 시간을 보냈다. 알고리즘을 새로운 방법으로 짜보기도 하는 등 여러가지 시도를 해보았다. 

여러가지 시도를 하면서 중점을 맞춘 내용은 어떤 상황이더라도 Pivot을 기준으로 최대한 동등하게 배열을 나누는 것 이었다.

생각하기까지 매우 오랜시간이 걸렸지만 결과적으로는 매우 간단하게 해결할 수 있었다.

바로 배열의 가운데값을 피봇으로 설정하는 것이다.

물론 실제 가운데 값을 피봇으로 설정한 후 알고리즘을 실행시키면 제대로 정렬되지않을 뿐더러 데이터가 엉망이된다.

그래서 조금만 비껴생각해낸 것이 배열의 가운데 값을 left값과 교환하는 것이다. 그 이후의 방법은 기존알고리즘과 동일하다.

바뀐 코드는 아래와 같다.

이 아래로는 이전의 코드와 동일하다.

핵심적인 부분은 바로 median을 설정하는 부분과 그것을 left(원래의 피벗)과 교환하는 부분이다.

median을 배열의 가운데 요소로 선택하고 이것을 다시 피벗과 교환함으로써 피벗이 가장 큰값이나 작은 값이 아닌 중간값으로 설정된다.

때문에 오름차순이나 내림차순으로 미리 정렬된 배열의 경우에도 동등한 2개의 배열을 만들어 낼수 있으며 

이는 곧 퀵정렬의 강점을 살릴 수 있게 된다는 것이다.

위의 코드를 이용하여 실제로 테스트를 해본 결과는 아래와 같다.

기존의 알고리즘 

요소 수 :           100,000                  100,000,000   

랜덤 배열 :         0.017                        23
역순 배열 :         12.89            너무 오래걸려서 측정 불가
순열 배열 :         13.21             너무 오래걸려서 측정 불가

Median피벗 알고리즘

요소 수 :           100,000                  100,000,000   

랜덤 배열 :         0.017                           23
역순 배열 :         0.0076                      8.98
순열 배열 :         0.0072                      8.46

이전 알고리즘에 비해서 매우 빠른 속도를 보여준다.

자동적 에이전트 (Autonomous Agent)란?

자동으로 움직이며(행동하며) 현재 혹은 미래의 상황을 감지하고 그에 따른 적절한 반응을 보여주는 AI객체라고 생각한다.

AI 프로그래머가 디자인 하기에 따라 무엇을 찾는 다거나 무엇으로 부터 숨는다거나, 집단적인 행동을 한다거나 독자적으로 배회하는 등의 행동을 할 수 있다.

앞으로의 포스트에서 여러가지 행동으로 디자인된 에이전트들의 모습과 구현 방법에 대해 이야기 하겠다.

본 내용은 "실용적 예제로 본 게임 인공지능 프로그램하기"라는 책을 읽은 후 배운 내용을 바탕으로 정리하는 것이다.

Seek - 찾기

가장 먼저 이야기할 행동은 목표 타겟을 찾는 행동인 Seek이다.

결과를 먼저 보자면 위의 그림처럼 진행하던 방향에서 목표지점을 향해 점차적으로 방향을 틀어 이동하는 모습을 볼 수 있다.

원리를 설명하기에 앞서 조종행동에서 중요하게 사용되는 벡터에 대해 설명하겠다.

조종행동에서 빠질 수 없는 것이 바로 벡터(Vector)이다. 

벡터는 스칼라와 동일하게 ( X, Y )으로 표현하지만 의미는 매우 다르다. 

스칼라 포인트 ( 3 , 3 )의 경우 ( 0, 0 )을 기준으로 하는 좌표계에서 아래와 같은 점으로 표시된다.

하지만 벡터의 경우 ( 0, 0 )을 기준으로 ( 3, 3 )을 표현하면 아래와 같다.

이렇게 화살표로 표현되는 이유는 스칼라는 단순히 좌표 즉, 위치에 대한 정보만 가지고 있지만 벡터의 경우 위치와 방향의 정보를 가지고 있기 때문이다.

때문에 같은 ( 3, 3 )의 정보라도 벡터값인지 스칼라 값인지에 따라 의미하는 것은 다를 수 있다.

간단하게나마 벡터에 대한 설명을 했고 본격적으로 찾기 조종행동에 대해 알아 보겠다.

원리는 다음의 그림과 같다.

첫번째 그림에서 보이듯이 에이전트는 C의 속도(방향)로 이동 중 이었다. 그러던 중 Goal을 찾게 되었고 목표지점으로 설정한 후 도달하길 원하고 있다.

Goal에 도달하기 위한 원하는 속도(T)는 다음의 공식으로 구할 수 있다.

G(Goal) - 현재위치(P) = 원하는 속도(T)  => T = G - P

G라는 포인트, 스칼라값에서 P라는 포인트, 스칼라값을 빼면 바로 T라는 벡터를 얻을 수 있다. 스칼라 - 스칼라 = 벡터이기 때문이다.

원하는 속도는 구하였다. 그렇다면 어떻게 C에서 T로 속도를 바꿀 수 있을까?

간단하게는 그냥 현재 P의 속도를 T로 바꿔만 주면 해결될 것이다.

하지만 그렇게 하면 Goal을 향해서 직선으로 이동할 뿐 내가 원하는 느낌인 커브를 도는것을 볼 수 없다.

답은 두번째 그림에서 찾을 수 있다. 

바로 조종힘인 D를 구하고 그것을 현재 속도에 점차적으로 더해주면 된다.

조정힘을 구하는 공식은 다음과 같다.

원하는 속도(T) - 현재속도(C) = 조종힘(D)   =>  D = T - C

이제 계산되어 나온 D를 현재 속도에 더해주면 에이전트가 점차적으로 방향을 트는 것을 확인 할 수있다.

코드

+ 후에 동영상을 올릴 수 있으면 추가하겠다.

평균적으로 가장 빠르다는 QuickSort!!

사실 좀 많이 실망했다. 결과를 먼저 말하자면 랜덤 배열일 경우 shellsort보다 5배 정도 빠르다지만 

순열이나 역순일 경우 시간측정이 무의미 할 정도로 오래 걸렸다.(1억개의 배열 기준)

물론 퀵솔트의 원리를 알고 최악의 경우 O(n^2)인 것을 생각해보면 당연하다고 할 수 있으나 그래도 기대했던 만큼의 속도가 나오지 않았다.

stl의 qsort는 quicksort만으로 이루어진 것은 아닌 듯 하다. 

원리

1. 피벗(pivot)이라는 값을 기준으로 더 큰 수는 pivot의 오른쪽 작은 값은 왼쪽으로 정렬시킨다.

2. 정렬이 완료되었으면 피벗을 기준으로 두개의 배열로 나눈다.

3. 나누어진 배열을 다시 1번 부터 재귀적으로 반복한다.

특징

1. 랜덤배열에서 빠른 정렬 속도를 보인다.

2. 피벗(pivot)을 선정하는 방법에 따라 속도가 달라진다.

3. 순열이나 역순의 경우 매우 느린 속도를 보인다.

4. 재귀함수 기반으로 구현시 복잡하게 생각될 수 있다.

연산시간

1. 평균적인 경우(랜덤) : O(n log n)

2. 최악의 경우 :   = n(n-1) / 2 

3. O표기법으로는 O(n^2)이 된다.

코드

결과

요소 수 :           100,000               100,000,000   

랜덤 배열 :         0.017                     23
역순 배열 :         12.89               너무 오래걸려서 측정 불가
순열 배열 :         13.21               너무 오래걸려서 측정 불가

결론

[QuickSort_ver1]의 경우 일반적인 방법으로 pivot설정을 가장 왼쪽 요소로 하였다.

시간측정에서 보여지듯이 랜덤배열의 경우 매우 빠른 속도를 보여주지만 순차배열이나 역순배열의 경우 매우 오랜 시간이 걸렸다. 

그 이유는 이후에 [피벗설정에 따른 퀵정렬의 속도] 같은 포스트를 통해 이야기 하도록 하겠다.

ShellSort 는 뭐라하지.. 조개껍질?? 은 아니고 창안자인 도널드 셸을 따서 이름 지었다고 한다.

원리

1. [InsertionSort]와 마찬가지로 현재요소의 제 자리를 찾는 과정이 필요하다.

2. 현재요소( current )가 현재요소 - H( current - H ) 보다 작다면 교환이 일어난다.(H는 H-Sequence)

특징

1. InsertionSort의 최대 장점인 거의 정렬된 배열의 경우 빠르다는 것을 잘 살린 알고리즘이다.

2. for문을 총 3중으로 사용하기 때문에 언뜻보면 O(n^3)으로 볼수 있다. 하지만 일정 Interval을 기준으로 jump하며 반복한다.

3. H-Sequence(= Interval)라고하는 개념을 통해 분할정렬한다.

4. 매우 먼 거리의 요소들을 한번에 가까운 거리로 옮기면서 정렬하기 때문에 교환이 적게 일어난다.

연산시간

1. 최악의 경우 :   = n(n-1) / 2 

2. O표기법으로는 O(n^2)이 된다.

코드

결과

요소 수 :           100,000               100,000,000   

랜덤 배열 :         0.036                      105
역순 배열 :         0.012                       17
순열 배열 :         0.0074                    13.6     

결론

InsertionSort를 변형하여 구현하였다.

구현하면서 느낀점은 InsertionSort의 단점을 상당부분 보안한 알고리즘이라는 것이다.(한번에 많은 이동을 한다는 점에서)

위의 코드와 결과를 보면 알수 있듯이, 구현은 간단하지만 성능은 무시할 수 없는 알고리즘이다. 

특히 역순이나 순열의 경우 QuickSort보다 빠른 속도를 보였다.

적절한 상황에 사용하면 좋은 정렬알고리즘이다.

셋째는 InsertionSort, 삽입 정렬이다.

원리

1. 0부터 끝요소까지 반복한다.( current < N )

2. 현재요소의 제 자리를 찾는 과정이 필요하다.

3. 현재요소( current )가 현재요소 - 1( current - 1 ) 보다 작다면 교환이 일어난다.

특징

1. 많은 교환 횟수를 가진다.

2. 이미 정렬되어진 배열의 경우 n - 1번의 비교연산만 수행할 뿐 더 이상의 교환이나 비교연산이 일어나지 않아 빠르다.

연산시간

1. 최선의 경우 : N - 1번

2. 최악의 경우 :   = n(n-1) / 2 

3. 처음에는 1번 비교하며 N-1번 비교까지 반복한다.

O표기법으로는 O(n^2)이 된다.

코드

결과

랜덤 배열 : 10.60
역순 배열 : 18.70
순열 배열 : 0.00056

결론

이미 정렬이 되어 있는경우 비교를 한번만 한다는 점이 인상적이다. ( 다른 정렬의 경우 교환은 안일어나지만 전체적인 비교는 일어난다. )

이점을 이용하면 좋은 알고리즘을 구현할 수 있을 것 같다.

둘째는 BubbleSort, 버블 정렬이다.

원리

1. 0부터 끝요소까지 반복한다.( current < N )

2. 현재요소( current )와 다음 요소 ( current + 1 )를 비교하여 다음 요소가 더 작으면 교환이 일어난다.

3. 가장 뒤부터 정렬이 일어난다.

특징

1. 많은 횟수를 비교, 교환 하기 때문에 속도가 느리다.

2. pass. 1에서 교환이 일어나지 않을 경우 이미 정렬되어 있는 배열이지만 이것을 확인하지 못하고 정렬을 계속 시도한다. 

연산시간

1. 처음에는 N-1번 비교하여 가장 큰 수를 맨뒤로 밀어낸다.

2. 그렇게 [ (N - 2) + (N - 3) + (N - 4) + ... + 1 ] 만큼 비교 및 교환을 수행한다.

3. 식으로 나타내면   = n(n-1) / 2 이며 O표기법으로는 O(n^2)이 된다.

코드

결과

랜덤 배열 : 33.80
역순 배열 : 22.30
순열 배열 : 17.60

결론

버블정렬은 구현하기가 가장 쉬웠던 것 같다.

하지만 이미 정렬된 배열에 대해서 알지 못하고 모두 비교해보기 때문에 적절한 대처방안이 필요할 것 같다. 대처 방안은 언젠가 추가할 것이다.

역시 O(n^2)의 알고리즘 답게 요소가 많아질 수록 응답 시간이 길어졌다.