'알고리즘'에 해당되는 글 1건

  1. 2008.04.16 소팅의 총정리



삽입정렬


이미 정렬되어 있는 곳에 새로운 레코드를 '삽입(Insertion)하는 방식이다. 정렬되어 있지 않은 랜덤값의 경우에는 맨 앞의 단 한 개의 레코드가 정렬되어있다고 가정하고 정렬을 시작하게 된다.

두 번째 값을 읽었을 때에는 이미 정렬되었다고 여긴 첫 번째 값과 비교하여 순위를 정하고 두 개만 가지고 자체적으로 정렬을 한다. 세 번째 값을 읽었을 때에는 이미 정렬된 앞의 두 값과 비교하여 세 번째 값의 크기에 적합한 위치로 정렬되어 들어가게 된다.데이터의 크기만큼 위와 같은 단계를 반복한다.

이미 정렬된 앞의 값들과 새로 들어올 값의 비교를 위해서, 하나의 값이 들어갈 때마다 가장 오른쪽의 최고로 큰 수부터 하나씩 크기비교를 하게 되며, 들어가려고 하는 값보다 더 작은 값이 나올 때까지 계속 왼쪽으로 가면서 크기비교를 해서 드디어 더 작은 값을 찾았을 때 그곳의 오른쪽에 새로 들어올 값이 삽입(Insertion)되는 방식이다.

따라서 만약 큰 배열에 Insertion Sort를 행할 때 큰 값의 경우에는 정렬이 빠르게 되지만 작은 값들이 많이 입력되면 뒤에서부터 계속 하나씩 비교해야만 하므로 효율이 떨어질 수 있다. 또한 하나의 값을 입력하였을 때 평균적으로 전체 배열의 반과 비교해야만 함을 알 수가 있다.

Insertion Sort의 이러한 특성을 알고 적절한 곳에 사용하면 좋을 것이다.

다음 그림을 통해 insertion sort의 방법을 알아보도록 하자.

예제 그림

입력된 초기값은 16, 7, 3, 5 이다.

일단 16만 정렬된 상태라 '가정' 한다. 그러면 다음자리에 위치한 7이 새로 들어올 값이 된다. 16과 7을 비교하여 7이 더 작으므로 7이 16을 넘어 왼쪽으로 가게 된다. 더 이상 비교할 것이 없으므로 7, 16의 순으로 완전히 정렬된 배열이 된다.

세 번째에 위치한 값인 3은 이미 정렬된 배열 (7, 16) 의 가장 오른쪽 숫자인 16과의 비교를 거치게 된다. (7,16,3)의 정렬되지 않은 배열에서 먼저 16과 3을 비교하여 16이 더 크므로 16을 한칸 뒤로 옮기고 다음숫자인 7과 비교하게 된다. 7이 더 크므로 7역시 한칸 뒤로 옮겨지고 3은 맨 앞자리로 가게 된다.

이제 (3, 7, 16)으로 이미 정렬된 배열에 5를 추가하는 일만 남았다. 지금까지 해온 것처럼 가장 오른쪽에 있는 16과 5를 비교하게 된다. 5는 16보다 작으므로 16을 오른쪽으로 한 칸 옮기고, 왼쪽에 있는 7과 다시 비교하게 된다. 7보다도 작으므로 7을 오른쪽으로 한 칸 옮기고, 그 왼쪽의 3과 비교한다. 3보다는 크므로 5는 3과 7 사이에 들어가야 함을 알 수가 있다. 따라서  임시변수에 있던 5가 7과 16의 이동을 통해 확보된 공간에 들어감으로써 정렬이 완성된다.

삽입정렬의 동작 알고리즘

  1. 정렬 할 레코드를 임시 변수에 저장한다
  2. 정렬 할 레코드와 앞의 정렬된 레코드와 비교하여
  3. 정렬 할 레코드의 값이 더 작으면
  4. 정렬 된 레코드를 한칸 뒤로 옮기고
  5. 한칸 더 앞의 레코드와 비교한다.
  6. 정렬할 레코드의 값이 더 크면
  7. 현재위치에 임시변수에 저장된 값을 넣는다.
     
  • Sorting Method
        for (i=1; i<n; i++)
        {

              임시변수=list[i];
              for(i-1번째부터 정렬 할 레코드보다 정렬된 레코드값이 더 클 동안 하나씩 감소)
                   {
                  정렬된 레코드를 하나씩 뒤로 옮긴다.;
                   }
              list[j+1]=임시변수;
          }


버블정렬

Bubble Sort는 가장 기본적이고 초보적인 Sorting 방법으로써, 서로 인접한 데이터들을 뒤에서부터 자리바꿈하면서 정렬하는 방법이다. (Selection Sort는 앞에서부터 정렬한다.)

효율성은 떨어지나, 구현이 간단하여 속도가 별로 중요하지 않은 경우에 널리 쓰이는 방법이다.

입력자료 :

4

7

3

1

5

8

2

6

  1. 4와7을 비교한다. 7이 더 크므로 변화 없다.

    -->

    4

    7

    3

    1

    5

    8

    2

    6

     

     

     

     

     

     

     

  2. 7과 3을 비교한다. 3이 더 작으므로 바꾼다. 

    -->

    4

    7

    3

    1

    5

    8

    2

    6

     

     

     

     

     

     

     

  3. 7과 1을 비교한다. 1이 더 작으므로 바꾼다.

    -->

    4

    3

    7

    1

    5

    8

    2

    6

     

     

     

     

     

     

     

  4. 7과 5를 비교한다. 5가 더 작으므로 바꾼다.

    -->

    4

    3

    1

    7

    5

    8

    2

    6

     

     

     

     

     

입력자료 :

4

7

3

1

5

8

2

6

  1. 7과 8을 비교한다. 8이 더 크므로 변화 없다.

    -->

    4

    3

    1

    5

    7

    8

    2

    6

     

     

     

     

     

     

     

  2. 8과 2을 비교한다. 2가 더 작으므로 바꾼다. 

    -->

    4

    3

    1

    5

    7

    8

    2

    6

     

     

     

     

     

     

     

  3. 8과 6을 비교한다. 6이 더 작으므로 바꾼다.
    --> 4 3 1 5 7 2 8 6
                 

Pass 1 결과 : 4   3   1   5   7   2   6   8

Pass 1을 거치면 마지막 부분이 완전히 결정되어 더 이상 정렬대상이 되지 않는다. 따라서 마지막 부분을 뺀 나머지 7개의 숫자를 가지고 다시 Bubble Sort를 반복한다. 이 Pass 2 과정이 끝나면 마지막에서 두 번째 부분도 완전히 결정된다. 이런식으로, 정렬대상이 가장 처음의 숫자가 될 때까지 위의 계산을 반복한다.

버블정렬의 동작 알고리즘

  1. 첫번째 레코드와 두번째 레코드를 비교한다.
  2. 두번째 레코드값이 더 크면 바꾸지 않고
  3. 두번째 레코드값이 더 작으면 바꾼다.
  4. 두번째 레코드값과 세번째 레코드값을 비교한다.
  5. 이를 n번째 레코드까지 반복한다.
  6. 그러면 제일 큰값이 n번째에 위치하게된다.
  7. 첫번째 레코드와 두번째 레코드를 비교한다.
  8. 두번째 레코드값이 더 크면 바꾸지 않고
  9. 두번째 레코드값이 더 작으면 바꾼다.
  10. 두번째 레코드값과 세번째 레코드값을 비교한다.
  11. 이를 n-1번째 레코드까지 반복한다.
  12. 그러면 그다음으로 큰값이 n-1번째에 위치하게 된다.
  13. 이를 반복한다.
  • Sorting Method
         for(i는 n-1에서 1보다 클동안 i--)
            for(j는 0에서 i보다 작을동안 j++)
                if(j번째 레코드가 j+1번째 레코드보다 크면)
                    j번째 레코드와 j+1번째 레코드를 바꾼다.


선택정렬

가장 간단한 Sort알고리즘중의 하나인 Selection Sort의 정렬방식은, 루프를 돌 때마다 정렬대상범위중에서 가장 작은 수를 선택하여 그 위치를 바꾸어 나가는 방식이다.

속도면에서는 버블정렬이나 삽입정렬보다는 빠른 정렬에 속한다.

예를 통하여 알아보면 다음과 같다.

  • 처음 데이터는 3이다. 그 다음 데이터를 하나하나 읽으면서 가장 작은 수를 발견하여 처음 데이터와 위치를 바꾼다. 여기서는 4번 째 데이터인 1이 3보다 작으므로 1과 3의 위치를 바꾼다. 

    입력자료

    3

    6

    8

    1

    7

     

     

     

     

     

     

     

     

     

     

  • 두 번째 데이터는 6이다. 그 다음 데이터를 하나하나 읽으면서 가장 작은 수를 발견하여 두 번째 데이터와 위치를 바꾼다. 여기서는 4번째 데이터인 3이 6보다 작으므로 3과 6의 위치를 바꾼다.

    Pass 2 :

    1

    6

    8

    3

    7

     

     

     

     

     

     

  • 세 번째 데이터는 8이다. 그 다음 데이터를 하나하나 읽으면서 가장 작은 수를 발견하여 세 번째 데이터와 위치를 바꾼다. 여기서는 4번째 데이터인 6이 8보다 작으므로 6과 8의 위치를 바꾼다.

    Pass 3 :

    1

    3

    8

    6

    7

     

     

     

     

     

     

     

     

     

     

  • 네 번째 데이터는 8이다. 그 다음 데이터를 하나하나 읽으면서 가장 작은 수를 발견하여 네 번째 데이터와 위치를 바꾼다. 여기서는 5번째 데이터인 7이 8보다 작으므로 7과 8의 위치를 바꾼다.

    Pass 4 :

    1

    3

    6

    8

    7

     

     

     

     

     

     

     

     

     

     

  • 정렬이 끝난 모습이다.

    Pass 5 :

    1

    3

    6

    7

    8

     


선택정렬의 동작 알고리즠
  • Sorting Method Algorithm
  1. 첫 번째 레코드값을 전체 데이터중에서 가장 작은 값과 바꾼다. 가장 작은 값은 데이터 전체를 순차적으로 탐색하여 얻는다.
  2. 두번째 레코드값을 그 이하 레코드값중 가장 작은 값과 바꾼다.
  3. 모두 정렬될 때까지 이와같이 반복한다.

 

  • Sorting Method


for(i는 0에서 레코드 총 갯수-1개 만큼 하나씩 증가)
    min=i;
      for(j는 i+1에서 총갯수까지 하나씩 증가)
           if(j번째 레코드값이 min번째 레코드값보다 작으면)
               min=j;
swap(i,min);


퀵정렬

퀵 정렬은 C.A.R. Hoare가 만든(The Computer Journal, 5:10-15, 1962.) 가장 우수한 편에 속하는 평균 수행능력을 갖는 정렬 방식이다. (단, 조건에 따라서는 분포수 정렬, 역사상 정렬, 래딕스 정렬방법이 빠르다.)
버블정렬이나 선택정렬의 경우, 바로 옆의 데이터를 서로 비교하여 교환하는 방식인데, 이러한 방식은 데이터가 최종으로 정렬될 위치에서 멀면 멀수록 비효율적이라고 할 수 있다.

퀵 정렬은 멀리 떨어진 데이터를 서로 교환함으로써 이러한  비효율성을 개선하였다. 간단히 설명하면, 'Pivot' 이라 불리는 임의의 값을 설정한 후에 배열의 양끝방향에서부터 탐색을 시작해서 Pivot값보다 큰 값과 작은값을 발견하여 서로 치환하는 방식이다.

단점으로는, Pivot 값이 같은 것끼리의 순서관계가 파괴된다. 이러한 것이 매우 중요한 데이터의 경우 퀵소트를 쓰지 않는 것이 바람직하다.

예제를 보면서 수행과정을 자세히 알아보도록 하자.

다음과 같은 값들이 입력되었다고 하자.

입력값 :

26

5

37

1

61

11

59

15

48

19

Step 1 :

26

5

19

1

61

11

59

15

48

37

 

 

 

 

 

 

 

 

여기에서는 Pivot값을 맨 왼쪽 값으로 정한다고 가정한다.(임의의 키값 혹은 맨 오른쪽의 값이어도 상관없다.) 따라서 처음 Pivot값은 '26'이 된다. 다음엔 맨 왼쪽에서 오른쪽으로 가면서 Pivot값보다 큰값을 찾고(3번째값인 '37'이 되겠다.), 맨오른쪽에서 왼쪽으로 가면서 Pivot값보다 작은값(10번째 인 '19'가 되겠다.)을 찾아 바꾼다.

Step 2 :

26

5

19

1

15

11

59

61

48

37

 

 

 

 

 

 

 

 

쪽포인터와 오른쪽포인터가 위치한 곳에서부터 시작하여 계속해서 왼쪽포인터는 오른쪽으로 가면서 Pivot값보다 큰값을, 오른쪽포인터는 왼쪽으로 가면서 Pivot값보다 작은값을 찾는다. 따라서 이번엔 '61'과 '15'을 찾아 바꾸게 된다. 


Pass 1 : 11 5 19 1 15 26 59 61 48 37
                   
마찬가지로 반복하면 이번엔 왼쪽포인터는 '59'를 오른쪽 포인터는 '11'을 가리키게 된다. 이렇게 왼쪽포인터와 오른쪽포인터가 엇갈리게되면 마지막에 찾은가장 작은값과 Pivot값을 바꾼다. 즉 '11'과 '26'을 바꾼다.
 
Step 1 :

[ 11

5 1 19

15 ]

26

[ 59

61 48

37 ]

               
이렇게 마치고나면, Pivot값을 중심으로 왼쪽에는 Pivot값보다 작은 값들이, 오른쪽에는 Pivot값보다 큰 값들이 놓여지게 된다. 이것이 Quick Sort의 한 단계이다.

이번엔 위의 과정을 Pivot값의 오른쪽에 위치한 레코드들에 대해서 반복한다. 즉, 처음 Pivot값은 맨처음의 '11'이 되고, 맨왼쪽에서 Pivot값인 '11'보다 큰값인 '19'와 맨오른쪽에서 Pivot값보다 작은 값인 '1'을 찾아 바꾼다.

Pass 2 :

[ 1

5 ]

11

[19

15 ]

26

[ 59

61 48

37 ]

                   

다음에는 왼쪽포인터와 오른쪽포인터가 엇갈리게되므로, 그 다음에 찾은 가장 작은 값인 '1'와 Pivot값인 '11'을 바꾼다.


 

이를 계속해서 반복한 결과는 다음과 같다.

Pass 3 : 1 5 11 [19 15 ] 26 [ 59 61 48 37 ]
                     
Pass 4 : 1 5 11 15 19 26 [ 59 61 48 37 ]
                     
Pass 5 : 1 5 11 15 19 26 [ 48

37]

59

[61]
                     
Pass 6 : 1 5 11 15 19 26 37 48 59 [61]
                     
Pass 7 : 1 5 11 15 19 26 37 48 59 61


퀵정렬 동작 알고리즘

  1. 키(Pivot)값을 선택한다.
  2. 레코드의 왼쪽에서부터 오른쪽으로 Pivot값보다 큰값을 찾는다.
  3. 레코드의 오른쪽에서부터 왼쪽으로 Pivot값보다 작은값을 찾는다.
  4. 2,3에 의해 찾은 값을 서로 바꾼다.
  5. 2,3의 포인터가 교차할때까지 반복한다.
  6. 포인터가 교차할 경우, 오른쪽포인터가 찾은 값과 Pivot값을 교환한다.
  7. 앞의 순서를 반복한다.

퀵정렬의 pivot 값 선택

퀵 정렬의 Pivot값은 배열의 가장 처음값이나 끝값등 마음대로 설정할 수 있으나, 가장 좋은 것은 배열안에 있는 모든 값의 평균값이다. 평균값이 Pivot이 되면 첫 Pass에서 평균값보다 큰 배열, 그리고 작은 배열이 반반씩 균등하게 나뉘어지므로 최고의 효율을 낼 수 있다. 너무 크거나 작은 값이 Pivot으로 선정되면 최악의 경우 한쪽 배열에 한 개, 또 한쪽 배열에 나머지 부분이 들어갈 수도 있다. 이때는 자기 호출의 깊이가 n정도가 되며 실행 시간이 n2에 비례하는 정도로 떨어진다.

퀵 정렬의 Pivot값은 보통 배열의 처음값, 혹은 끝의 값을 취하지만 한번의 탐색을 통해 평균을 내어 그 평균과 가장 가까운 값을 Pivot값으로 설정하게 만들면 효율을 높일 수 있다. 그런데 최적의 Pivot값을 찾을 때 오히려 최악의 Pivot값이 선정되어 Sort를 진행할 경우보다 더 많은 비용이 들 수도 있으므로 이러한 구현을 추가할 때는 상황을 보아 신중하게 결정해야 하겠다.

퀵정렬과 삽입정렬의 조화

퀵 정렬은 무작위한 배열을 정렬하는데는 매우 빠르지만 구간이 넓을 경우에 한하고 구간이 어느정도 좁혀지면 그다지 빠르지 않으므로 적당한 점까지 퀵 정렬을 한 후, 다음은 삽입정렬로 대체한다. 삽입정렬은 대충 정렬한 데이터를 다시 정렬할 때 진가를 발휘한다.

재귀형 퀵정렬의 자바코

Private static void quickSort(Comparable [ ]a, int left, int right)
{
    if(left + CUTOFF <= right)
    {
        Comparable pivot = median3(a, left, right); // Pivot 값으로 중간값을 설정한다.
        //분할 시작
        int i=left, j=right-1;
        // i, j 는 배열의 처음과 끝을 나타내는 배열의 첨자(subscript)이다.
        for(;;)
        // Pivot 원소를 중심으로 두 부분으로 나눈다.
        {
            while(a[++i].compareTo(pivot) < 0) { }
            // 배열의 앞에서부터 차례대로 Pivot원소보다 작은
원소들은 그대로 두고,
            // 큰 원소를 만나면 i값을 늘리지 않고, 루프문을 빠져나간다.

            while(a[--j].compareTo(pivot) > 0) { }
            // 배열의 앞에서부터 차례대로 Pivot원소보다 큰
원소들은 그대로 두고,
            // 작은 원소를 만나면 j값을 늘리지 않고, 루프문을 빠져나간다.

            if(i<j)
                swapReferences(a, i, j);
                //
위의 두 루프문에서 각 부분리스트에 속할 원소들이 아닌 원소들은
                // 서로 자리를 바꾸어 준다.

            else
                break;
        }
 
        swapReferences(a, i, right - 1);  // Pivot 원소를 두 부분리스트 사이에 위치시킨다.
       
        // 각 두 부분리스트에 대해서 위의 과정을 반복한다.
        quicksort(a, left, i-1);  // Pivot 보다 작은값들을 정렬한다.
        quicksort(a, i+1, right); // Pivot 보다 큰 값들 정렬한다.
    }
    else    // 작은 배열에서는 삽입정렬을 사용함으로서 효율을 증대시킨다.
        insertionSort(a, left, right)
}


비재귀형 퀵정렬의 C 코드

  #define MAX 12 
          typedef struct node { 
             int l, r; 
          } NODE; 
          void sort1(int a[], int l, int r) { 
             NODE stack[MAX]; 
             int i, j, x, temp, top = -1; 
             stack[top].l = l; stack[top].r = r; 
             do { 
                l = stack[top].l; r = stack[top--].r; 
                do { 
                   i = l; j = r; x = a[(l+r)/2]; 
                   do { 
                      while (a[i]<x) i++; 
                      while (a[j]>x) j--; 
                      if (i<=j) { 
                         temp = a[i]; a[i] = a[j]; a[j] = temp; 
                         i++; j--; 
                      } 
                   } while (i<=j); 
                   if (i<r) { 
                      stack[++top].l = i; stack[top].r = r; 
                   } 
                   r = j; 
                } while (l < r); 
             } while (top != -1); 
          } 


힙정렬

Heap Sorting은 Max Heap이라는 자료구조를 이용한 정렬방식으로 정렬하고자하는 레코드값들을 Heap이라는 특수한 구조에 저장한 다음 정렬후 root부분을 추출하고, 다시 재정렬후  root부분을 추출하는 것을 반복함으로서 정렬된 레코드를 얻어내는 방식이다.

힙정렬의 동작방식

다음과 같은 레코드들이 입력되었다고 하자. (입력값 :  5,1,15,11,19)

Max Heap에 의해 정렬되면 다음과 같이 된다.

root를 꺼내고 다시 정렬하면 다음과 같이 된다.

 


 

정렬값 : 19


정렬값 : 19, 15

계속해서 root를 꺼내고 정렬하는 것을 반복한다.

계속 반복한다.

 


 

정렬값 : 19, 15, 11


정렬값 : 19, 15, 11, 5

최종적으로 1만 남게 되며 정렬이 끝난다.


정렬값 : 19, 15, 11, 5, 1


  • Sorting Method Algorithm
  1. 정렬하고자 하는 레코드를 Heap에 넣는다.
  2. Heap을 정렬한다.
  3. Heap의 root를 추출한다.
  4. Heap을 재정렬한다.
  5. 2~4를 Heap이 Null이 될 때까지 반복한다.
힙정렬의 자바코드

class HeapSortAlgorithm extends SortAlgorithm {
  /**
   * Make the sub-array starting at position i into a a heap,
   * assuming that it's left and right children are already
   * heaps.
   */
  void reheap (int a[], int length, int i) throws Exception {
    boolean done = false;
    int T = a[i];
    int parent = i;
    int child = 2*(i+1)-1;
    while ((child < length) && (!done)) {
      compex(parent, child);
      pause();
      if (child < length - 1) {
        if (a[child] < a[child + 1]) {
          child += 1;
        }
      }
      if (T >= a[child]) {
        done = true;
      }
      else {
        a[parent] = a[child];
        parent = child;
        child = 2*(parent+1)-1;
      }
    }
    a[parent] = T;
  }
 
  /**
   * Sort the input using the heap sort algorithm.
   */
  void sort(int a[]) throws Exception {
 
    // Make the input into a heap
    for (int i = a.length-1; i >= 0; i--)
      reheap (a, a.length, i);
 
    // Sort the heap
    for (int i = a.length-1; i > 0; i--) {
      int T = a[i];
      a[i] = a[0];
      a[0] = T;
      pause();
      reheap (a, i, 0);
    }
  }
}

힙정렬의 C 코드

void heap_sort(int *list, int n)
{
     int i, temp;
     for(i=(n/2); i>=1; i--)   // 초기 힙 만들기
          adjust(list, i, n);
     for(i=(n-1); i>=1; i--) {  // 힙 정렬의 두 번째 단계
          temp = list[i+1];      // 마지막 노드와 뿌리 노드의 교환
          list[i+1] = list[1];
          list[1] = temp;
          adjust(list, 1, i);     // i개의 키에 대하여 adjust 적용
     }
}

void adjust(int *list, int i, int n)
// i : adjust 알고리즘을 시작하는 노드의 인덱스
// n : 전체 노드의 개수
{
     int j, k, done;

      done = 0;     // 아직 끝나지 않았음을 표시
      k = list[i];    // 뿌리 노드의 값, 즉 옮겨야 할 원소의 값
      j = 2 * i;       // i 노드의 좌 자 노드

      while ((j <= n) && (!done)) {    // 자식노드가 있고 not done일 때까지 반복
           if ( j < n)      // j + 1 <= n 과 마찬가지인데 우 자 노드의 존재를 검사
           if (list[j] < list[j + 1])      
           j ++;        // 자 노드들 중 큰 노드를 선택

           if (k >= list[j])
                done = 1;     // 자 노드보다 크므로 수행을 중단

           else{
                list[j / 2] = list[j];       // 자 노드를 부노드로 끌어 올림,
                                                // 자 노드에 k 값을 쓰지 않는 이유는 나중에
                                                // 수행이 다 끝난 다음에 쓰기 때문임.

                 j *= 2;
          }
     }
     list[j / 2] = k;   // 수행이 끝나면 찾아낸 위치에 맨 처음 저장한 뿌리 노드의 값을 저장
}




합병정렬

이미 정렬된 두 개 이상의 배열이 있을 때 이들을 합쳐서 하나의 정렬된 배열을 만드는 것이 바로 Merge Sort이다. 예를들어 (1,3,5,7)이라는 배열과 (2,4,6,8)이라는 배열이 있다면 이것을 합쳐서 (1,2,3,4,5,6,7,8)로 만드는 것이다.

합병 정렬에는 2원 합병정렬 (2-Way Merge Sort)과 N원 합병정렬 (N-Way Merge Sort)가 있다. 여기서는 2원 합병정렬로 설명한다.

2원 합병정렬의 동작방식

그러면 구체적으로 어떤 방식으로 두 개 이상의 배열을 하나로 만드는지 예를 통해서 알아보자. 밑의 그림에 있는 (1,3,4,7) 와 (2,5,6,8)의 배열을 하나로 만들기 위해 비어있는 8칸짜리 배열을 만들어놓았다. 각 배열의 맨 앞에는 화살표 표시가 되어 있는데, 이것은 인덱스를 뜻한다.

1

3

4

7

 

 

 

2

5

6

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

① 1과 2를 비교한다. 1이 작으므로 새 배열에 1이 들어가게 된다. 그리고 첫 번째 배열의 값이 새 배열에 들어갔으므로 첫 번째 배열의 인덱스를 오른쪽으로 한 칸 옮기고 새 배열의 인덱스도 오른쪽으로 한 칸 옮긴다.

1 3 4 7

 

 

 
2 5 6 8

 

 

 
1      

 

 

 

 

 

 

 

 

 

 

 

② 3과 2를 비교한다. 2가 작으므로 새 배열에 2가 들어가게 된다. 이번에는 두 번째 배열의 값이 새 배열에 들어갔으므로 두 번째 배열의 인덱스를 오른쪽으로 한 칸 옮기고 새 배열의 인덱스도 오른쪽으로 한 칸 옮긴다.

1

3

4

7


 

 

2 5 6 8

 

 

 
1 2    

 

 

 

 

 

 

 

 

 

 

 

③ 3과 5를 비교한다. 3이 작으므로 새 배열에 3이 들어간다. 새 배열의 인덱스는 변함없이 한 칸 오른쪽으로 옮겨지고, 3이 출력된 첫 번째 배열 역시 인덱스가 한 칸 옮겨지게 된다.

1 3 4 7

 

 

 
2 5 6 8

 

 

 
1 2 3  

 

 

 

 

 

 

 

 

 

 

 

④ 4와 5를 비교하여 작은쪽인 4가 새 배열에 들어가며 인덱스도 옮겨진다.

1 3 4 7

 

 

 
2 5 6 8

 

 

 
1 2 3 4

 

 

 

 

 

 

 

 

 

 

 

⑤ 7과 5를 비교하여 작은쪽인 5가 새 배열에 들어가며 인덱스도 옮겨진다.

1 3 4 7

 

 

 

2 5 6 8

 

 

 
1 2 3 4

5

 

 

 

 

 

 

 

 

 

 


⑥ 7과 6을 비교하여 작은쪽인 6이 새 배열에 들어가며 인덱스도 옮겨진다.

1 3 4 7

 

 

 

2 5 6 8

 

 

 
1 2 3 4

5

6

 

 

 

 

 

 

 

 

 

⑦ 7과 8을 비교하여 작은쪽인 7이 새 배열에 들어가며 인덱스도 옮겨진다.

1 3 4 7

 

 

 

2 5 6 8

 

 

 


1 2 3 4

5

6

7

 

 

 

 

 

 

 

 

⑧ 첫 번째 배열의 인덱스값이 첫 번째 배열 크기를 넘었다는 것은, 첫 번째 배열의 모든 값이 새 배열에 들어갔음을 의미한다. 따라서 두 번째 배열의 남은 값들을 차례대로 새 배열에 집어넣는다.

1 3 4 7

 

 

 

 

 

2 5 6 8

 

 

 

 

 

1 2 3 4

5

6

7

8

 

 

 

 

 

 

 

 

⑨ 만약 두 번째 배열의 인덱스값이 두 번째 배열 크기를 넘으면 이번에는 두 번째 배열의 모든 값이 새 배열에 들어갔음을 의미하므로 남은 첫 번째 값을 새 배열에 차례대로 집어넣으면 된다.

이로써 Merge Sort가 끝난다.


순서없는 배열을 정렬하기

Merge Sort는 본래 이미 정렬된 두 개 이상의 배열을 하나의 정렬된 배열로 만드는 것이지만 정렬되지 않은 배열을 정렬하는데도 쓸 수 있다. 정렬과정을 예를 통해 알아보도록 하자.

다음과 같은 값들이 입력되었다고 하자.

입력값 :

26

5

77

1

61

11

59

15

48

19

이들의 병합과정은 다음과 같다.

Pass 1 : [26] [5] [77] [1] [61] [11] [59] [15] [48] [19]
 
Pass 2 : [5 26] [1 77] [11 61] [15 59] [19 48]
 

Pass 3 : [1 5 26 77] [11 15 59 61] [19 48]
 

Pass 4 : [1 5 11 15 26 59 61 77] [19 48]
 

Pass 5 : [1 5 11 15 19 26 48

59

61 77]



즉, 원소 하나하나를 이미 정렬된 배열로 가정하여 두 개씩 병합한다. Pass 2가 되면 이미 정렬된 원소 2개짜리 배열 두 개를 또다시 Merge Sort한다. 이런식으로 계속 합병하며 정렬하면 마지막에는 정렬된 하나의 배열이 된다.

또다른 방법은 2차원 배열을 쓰는 것이다. 10개의 원소를 모두 독립된 배열로 인식하고 처리할 때(N원 병합정렬), 인덱스를 i,j,k,l,m,n,o,p,q,r,s 로 잡으면 매우 불편하다. 이때 이 인덱스를 2차원 배열로 잡으면 반복문을 통해 편하게 정렬할 수가 있다.

힙정렬의 자바코드

Class MergeSortAlgorithm extends SortAlgorithm {

  void sort(int a[], int lo, int hi) throws Exception {
    // Base case
    if(lo == hi) {
      return;
    }
 
    // Recurse
    int length = hi-lo+1;
    int pivot = (lo+hi) / 2;
    sort(a, lo, pivot);
    sort(a, pivot+1, hi);
 
    // Merge
    int working[] = new int[length];
    for(int i = 0; i < length; i++)
      working[i] = a[lo+i];
    int m1 = 0;
    int m2 = pivot-lo+1;
    for(int i = 0; i < length; i++) {
      if(m2 <= hi-lo) {
        if(m1 <= pivot-lo) {
          if(working[m1] > working[m2]) {
            a[i+lo] = working[m2++];
          }
          else {
            a[i+lo] = working[m1++];
          }
        }
        else {
          a[i+lo] = working[m2++];
        }
      }
      else {
        a[i+lo] = working[m1++];
      }
      pause();
    }
  }
 
  void sort(int a[]) throws Exception {
    sort(a, 0, a.length-1);
  }
}


힙정렬의 C 코드

typedef struct {


 

int key;


} element;


 

 

 

 

 


void merge(list,sorted,i,m,n)


element list[], sorted[];


int i,m,n;


{


 

int j,k,t;


 

j=m+1;


 

k=i;


 

while(i<=m && j<=n){


 

 

if(list[i].key<=list[j].key)


 

 

 

sorted[k++].key=list[i++].key;


 

 

else


 

 

 

sorted[k++].key=list[j++].key;


 

}


 

if(i>m)


 

 

for(t=j; t<=n; t++)


 

 

 

sorted[k+t-j].key=list[t].key;


 

else


 

 

for(t=i; t<=n; t++)


 

 

 

sorted[k+t-i].key=list[t].key;


}



내부정렬의 성능 비교


정렬
방식

알고
리즘

비교 횟수

기억
공간

비 고

평균

최악

삽입

① 삽입

0(n2)

0(n2)

n

 ㉠ 비교 횟수 : c=n(n-1)/4
     C
max=n(n-1)/2
     C
min=n-1

 ㉡ 특징 : 알고리즘 간단하고,
              매회 서브파일 크기 증가

② 쉘

0(n(log2n)2)

0(n2)

n

 ㉠ h = 1.72

 ㉡ 특징 : 인접한 간격만큼 떨어진
               레코드로 서브파일 구성

교환

③ 선택

0(n2)

0(n2)

n

 ㉠ 비교 횟수 : c=n(n-1)/2

 ㉡ 특징 : 삽입 정렬보다 비교횟수
               가 적음

④ 퀵

0(nlog2n)

0(n2)

n + 스택

 ㉠ 특징 : 가장 빠르지만,
              최악의 경우 0(n
2)

 ㉡ 스택이 필요



정렬
방식

알고
리즘

비교 횟수

기억
공간

비 고

평균

최악

교환

⑤ 버블

0(n2)

0(n2)

n

 ㉠ 비교 횟수 : c=n(n-1)/4
     C
max=n(n-1)/2
     C
min=n-1

 ㉡ 특징 : 알고리즘 간단하고, flag
               사용시 효율 증가

선택

⑥ 힙

0(nlog2n)

0(nlog2n)

n +  
포인터

 ㉠ 특징 : 수행 속도 빠름
             트리를 링크드 리스트로
             표현시 포인터가 필요함

병합

⑦ 2원
    병합

0(nlog2n)

0(nlog2n)

2n

 ㉠ pass 횟수 : log2n

 ㉡ 특징 : 보조기억장치 내에서
              정렬

배분

⑧ 기수

0(d(n+r))

0(n2)

(n+1)r

 ㉠ d : 데이터 자리수
     r : 큐의 수

 ㉡ 특징 : 기억공간 낭비 심함
              속도가 빠름





Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요