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)이 된다.


코드

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
42
43
44
45
//SHELLSORT
 
void insertionSort(int* array, int size, int interval)
{
    for (int i = interval; i < size; i++)     // i == (1 ~ size)
    {
        int temp = array[i];                   // 현재값 저장
        int tempidx = i;                       // 현재 인덱스 저장
 
        for (int j = i; 0 <= (j - interval) && temp < array[j - interval]; j -= interval)  
        {                                     // j == (i ~ 0)                                 
            array[j] = array[j - interval];    // (j) < (j - interval)이면 교환
            tempidx = j - interval;
        }
        array[tempidx] = temp;                 // 값 대입 
    }
}
void ShellSort(int* array, int size)
{
    for (int h = size; 1 <= h; h /= 2)
    {
        insertionSort(array, size, h);         // h값을 인자로 넘긴다.
    }
}
int const MAX = 5;                     // Max 값
int g_arr[MAX] = {0, };                // 배열 초기화
   
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);     // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);    // 역순 배열 생성
    RandomNumber(g_arr, MAX);         // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);         // 배열 출력
    printf("\n");
    clock_t start = clock();         // 시작 시간
    ShellSort(g_arr, MAX);             // ShellSort
    clock_t end = clock();             // 끝 시간
    
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);         // 배열 출력
    printf("\nTime : %f\n", ((double)(end-start)) / CLOCKS_PER_SEC);
}
 
cs


결과



시간

시간은 MAX 값 100,000 과  100,000,000으로 기준을 나누어 측정하였다.

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

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


결론

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

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

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

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

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

'All > Algorithm' 카테고리의 다른 글

자동적에이전트 - Seek  (0) 2016.01.17
QuickSort  (0) 2016.01.07
InsertionSort  (0) 2016.01.03
BubbleSort  (0) 2016.01.02
SelectionSort  (0) 2016.01.02

셋째는 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)이 된다.


코드

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
//INSERTIONSORT
 
void InsertionSort(int* array, int size)
{
    for(int i = 1 ;i < size ;i++ )        // i == (1 ~ size)
    {
        int temp = array[i];              // 현재값 저장
        int tempidx = i;                  // 현재 인덱스 저장
        for(int j = i ;0 <= (j - 1) && temp < array[j - 1] ;j-- )    // j == (i ~ 0) 
        {                                                            // (j) < (j - 1)이면 교환
            array[j] = array[j-1];
            tempidx = j-1;
        }
        array[tempidx] = temp;            // 값 대입 
    }
}
int const MAX = 5;                        // Max 값
int g_arr[MAX] = { 0, };                  // 배열 초기화
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);        // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);       // 역순 배열 생성
    RandomNumber(g_arr, MAX);             // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);             // 배열 출력
    printf("\n");
    clock_t start = clock();             // 시작 시간
    InsertionSort(g_arr, MAX);            // InsertionSort
    clock_t end = clock();                // 끝 시간
 
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);             // 배열 출력
    printf("\nTime : %f\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}
cs

결과



시간

시간은 MAX 값 100,000 을 기준으로 측정하였다.

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


결론

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

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

'All > Algorithm' 카테고리의 다른 글

QuickSort  (0) 2016.01.07
ShellSort  (0) 2016.01.05
BubbleSort  (0) 2016.01.02
SelectionSort  (0) 2016.01.02
Sort Algorithm  (0) 2015.12.28

둘째는 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)이 된다.


코드

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
//BUBBLESORT
 
void BubbleSort(int* array, int size)
{
    for(int i = 0 ;i < size ;i++)     // i == (0 ~ size)
    {
        for(int j = 0 ;j < (size - 1) - i ;j++ ){ // j == (0 ~ (size - 1) - i)
            if(array[j] > array[j+1]) // (j) > (j + 1) 이면 교환
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
int const MAX = 5;                    // Max 값
int g_arr[MAX] = { 0, };              // 배열 초기화
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);    // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);   // 역순 배열 생성
    RandomNumber(g_arr, MAX);         // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);         // 배열 출력
    printf("\n");
    clock_t start = clock();         // 시작 시간
    BubbleSort(g_arr, MAX);           // BubbleSort
    clock_t end = clock();            // 끝 시간
 
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);        // 배열 출력
    printf("\nTime : %f\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}
cs

결과



시간

시간은 MAX 값 100,000 을 기준으로 측정하였다.

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


결론

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

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

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

'All > Algorithm' 카테고리의 다른 글

ShellSort  (0) 2016.01.05
InsertionSort  (0) 2016.01.03
SelectionSort  (0) 2016.01.02
Sort Algorithm  (0) 2015.12.28
JUMPGAME_알고리즘  (0) 2015.12.28

+ Recent posts

티스토리툴바