[알고리즘] 비교 기반 알고리즘

내부정렬이란 정렬 중 전체데이터를 주기억 장치에 저장한 후 정렬을 수행하는 방식의 정렬입니다.

 

이러한 내부정렬에는 정렬방식에 따라 비교 기반 알고리즘과 데이터 분포 기반 알고리즘으로 나눌 수 있습니다.

 

비교 기반 알고리즘은 직접적인 데이터 비교를 통해 알고리즘을 수행하는 방식입니다.

 

이러한 비교 기반 알고리즘의 종류에는 선택정렬, 버블정렬, 삽입정렬, 셸정렬, 퀵정렬, 합병정렬, 힙정렬 등이 있습니다.

 

비교 기반의 알고리즘의 성능을 측정하는 방법은 키값의 비교횟수가 적으면 성능이 좋다고 할 수 있습니다.

 

비교 기반 알고리즘 중 선택정렬, 버블정렬, 삽입정렬, 셸정렬은 시간복잡도가 O(n^2)이며 퀵 정렬, 합병정렬, 힙정렬의 시간복잡도는 O(nlogn)입니다.

 

1. 선택정렬

선택정렬은 입력배열에서 가장 작은값부터 순서대로 선택해서 나열하는 방식을 의미합니다.

 

선택정렬의 처리과정은 아래와 같습니다.

1) 순서도

 

 

 

2) 알고리즘

SelectionSort(A[],n)
  {
    for(i=0;i<n;i++){ //n-1번 반복
      min = i;
      for(j=i+1;j<n;j++){
        if(A[j]<A[min]){
          min = j;
        
          A[i]와 A[min]의 자리바꿈
        }  
      }
    }
    return A;
  }

 

3) 성능과 특징

위 의사코드를 보시면 중첩반복문을 사용하는 것을 볼 수 있습니다. 따라서 선택정렬의 성능은 O(n^2)이 됩니다.

 

또한 선택정렬의 특징으로는 입력데이터의 순서에 민감하지 않다는 것입니다. 왜냐하면 순서에 상관없이 항상 처음부터 끝까지 반복을 하게 됩니다. 따라서 입력데이터의 상태와 상관없이 항상 동일한 성능을 가지게 됩니다.

 

그리고 선택정렬은 제자리 정렬 알고리즘에 속합니다. 왜냐하면 입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문입니다.

 

그리고 선택정렬은 안정적이지 않은 정렬 알고리즘에 속하게 됩니다.왜냐하면 순서대로 진행하면서 최소값과 현재의 값의 위치를 바꾸는 방식이기 때문입니다.

예컨대 입력데이터가 10,30(A),30(B),20로 주어졌을 때 선택정렬을 수행하면 30(A)와 20의 위치가 바뀌게 되어 10,20,30(B),30(A)가 됩니다.

 

2. 버블정렬

버블 정렬은 모든 인접한 두 데이터를 차례대로 비교하여 왼쪽 데이터가 더 큰 경우에는 오른족 데이터와 자리를 바꾸는 과정을 반복해서 정렬을 수행하는 방식입니다.

 

여기서 비교를 진행하는 방향이 왼쪽에서 오른쪽이라면 가장 큰 값부터 찾아서 오른쪽 끝에서부터 위치 시키며, 비교를 진행하는 방향이 오른쪽에서 왼쪽으로 진행한다면 가장 작은 값부터 찾아서 왼쪽 끝에서부터 위치시킵니다.

 

1) 알고리즘

BubbleSort(A[],n)
  {
    for(i=0;i<n-1;i++)
      for(j=0;j<n-1;j++)
        if(A[j]>A[j+1])
          A[j]와 A[j+1]의 위치를 바꾼다.
    retrun A;
  
  }

2) 성능과 특징

버블 정렬도 중첩반복문을 사용합니다. 따라서 버블정렬의 성능은 O(n^2)이 됩니다.

 

버블정렬은 인접한 두데이터가 동일할 경우 위치교환이 발생하지 않기 때문에 안정적이라고 할 수 있습니다. 그리고 입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문에 제자리 정렬 알고리즘이라고도 할 수 있습니다. 

 

버블 정렬은 선택정렬보다 데이터교환이 많이 발생합니다. 따라서 선택정렬보다 비효율적이라고 할 수 있습니다.

 

버블 정렬의 비효율을 개선하기 위해서 처리단계의 수를 줄이거나 인접한 두 데이터의 비교횟수를 줄임으로써 개선할 수 있습니다.

 

첫번째로 처리단계의 수를 줄이는 방법은 반복을 진행중에 자리바꿈이 발생하지 않으면 이미 정렬된 상태로 판단하여 이후의 처리단계를 수행하지 않고 종료하는 것입니다.

 

두번째로 인접한 두 데이터의 비교횟수를 줄이는 방법은 각 단계에서 왼쪽 또는 오른쪽으로 이동하면서 이미 제자리를 잡은 데이터에 대해서는 비교를 수행하지 않는 것입니다.

 

3) 개선된 버블정렬의 의사코드

BubbleSort(A[],n)
  {
    for(i=0;i<n-1;i++){
      Sorted = True; //이미 정렬된 상태라고 가정
      for(j=0;j<(n-1)-i;j++) //왼쪽에서 오른쪽으로 진행
        if(A[j]>A[j+1]){
          A[j]와 A[j+1]의 위치를 바꾼다.
        
          Sorted = False; //자리바꿈이 발생한 것은 정렬되지 않은 상태
        }
        if(Soreted)) break; //자리바꿈이 발생하지 않았으므로 반복문 종료
    }
    retrun A;

  }

 

4) 개선된 버블정렬의 성능과 특징

개선된 버블정렬의 특징으로는 입력데이터의 상태에 따라 성능이 달라집니다.

 

예컨대 입력데이터가 역순으로 주어진 경우 성능은 O(n^2)이 되며 원하는 순서로 이미 정렬 되어있는 경우 성능은 O(n)이 됩니다. 물론 앞서 설명한 것처럼 최악의 경우를 주로 사용하기 때문에 성능은 O(n^2)이 된다고 볼 수 있습니다.

 

3. 삽입정렬

삽입정렬은 주어진 데이터를 하나씩 뽑은 후 이미 나열된 데이터가 항상 정렬된 상태를 유지하도록 뽑은 데이터를 바른 위치에 삽입하여 정렬하는 방식입니다.

 

삽입정렬은 입력배열에서 정렬부분 A[0..k-1]과 미정렬부분A[k..n-1]로 구분하여 처리합니다.

 

처음에는 A[0]을 정렬부분으로, A[1..n-1]은 미정렬부분으로 취급한 후 시작합니다.

 

이때 미정렬부분A[k...n-1]에서 첫번째 데이터 A[k]를 뽑아 정렬부분 A[0..k-1]에서 제자리를 찾아서 A[k]를 삽입합니다.

 

그러면 정렬부분 A[0..k]가 되어 정렬상태를 유지하게 됩니다.

 

1) 알고리즘

 InsertionSort(A[], n)
  {
    for (i = 1; i < n; i++){
      val = A[i];
      for(j=i;j>0 && A[j-1]>val;j--)
        A[j] = A[j-1];
      A[j] = val;
    }
    retrun A;
  }

 

2) 성능과 특징

인접한 두 데이터가 정렬되지 않은 경우에만 위치 교환이 발생하기 때문에 안정적입니다. 그리고 입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문에 제자리 정렬 알고리즘이라고도 할 수 있습니다. 

 

그리고 버블정렬과 마찬가지로 입력데이터의 원래순서에 민감하여 입력데이터의 순서에 따라 성능이 달라집니다.

 

원하는 정렬순서의 역순으로 주어지는 경우는 최악으로써 O(n^2)이 되며 원하는 순서의 정렬상태로 주어지는 경우에는 O(n)이 됩니다. 따라서 일반적인 성능은 O(n^2)이라고 할 수 있습니다.

 

4. 셸정렬

삽입정렬은 현재 삽입하고자 하는 데이터가 삽입될 위치에서 많이 벗어나 있어도 한번에 한자리씩만 이동해서 찾아가야 한다는 단점이 있습니다. 이러한 삽입정렬의 단점을 보완하기 위해 셸정렬이 나타났습니다.

 

셸정렬은 처음에는 멀리 떨어진 두 데이터를 비교하여 필요할 경우 위치를 교환하고 점점 가까운 위치의 데이터를 비교 및 교환 한 뒤 마지막에는 인접한데이터를 비교 및 교환하는 방식입니다.

 

이러한 방식은 입력배열을 부분 배열로 나누어 삽입정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 반복하는 것입니다.

 

이러한 부분배열을 나눌때 순열을 사용합니다. 순열의 역순으로 부분배열의 개수를 적용합니다.

 

 

1) 알고리즘

ShellSort(A[],n)
  {
    for(i=n/2;i>0;i=i/2){
     for(j=i;j<n;j++){
       val = A[j];
       for(k=j;k>=i && A[k-i]>val;k=k-i)
         A[k]=A[k-i];
       A[k] = val;
     } 
    }
     retrun A;
  }

 

2) 성능과 특징

이러한 셸정렬에서 하나의 입력배열 A[]을 물리적으로 여러개의 부분배열로 분할하는 것이 아니라 각 부분배열을 번갈아 가면서 미정렬부분의 첫번째 데이터를 뽑은 후 i만큼 떨어진 정렬부분에서 제자리를 찾아서 삽입하는 방식입니다.

 

또한 어떤 순열을 사용하느냐에 따라 성능이 달라집니다. 사용하는 순열에 따라 성능이 최선(O(nlogn))에서 최악(O(n^2))까지 차이가 납니다.

 

입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문에 제자리 정렬 알고리즘이라고 할 수 있습니다. 그리고 안정적이지 않은 정렬 알고리즘입니다.

 

5. 퀵정렬

퀵정렬이란 특정데이터를 기준으로 주어진 배열을 2개의 부분 배열로 분할하고 각 부분배열에 대해 퀵정렬을 순환적으로 적용하는 방식입니다. 또는 피벗이 제자리를 잡은 후 분할하여 정렬하는 방식입니다.

 

피벗이란?

주어진 배열을 두 부분 배열로 분할하는 기준이 되는 특정데이터를 의미합니다. 보통 주어진 배열의 첫번째 데이터를 피벗으로 지정합니다. 

1) 퀵 정렬의 알고리즘

QuickSort(A[],n)
  {
    if(n >1){
      //피벗을 기준으로 두 부분배열로 분할
      //pivot은 제자리를 잡은 피벗의 인덱스를 표시
      pivot = Partition(A[0,...n-1],n);
      //왼쪽 부분배열에 대한 퀵 정렬의 순환 호출
      QuickSort(A[0,...pivot-1],pivot);
      //오른쪽 부분배열에 대한 퀵 정렬의 순환 호출
      QuickSort(A[pivot+1,...n-1],n-pivot-1);
 
    }
  }

 

위 알고리즘에서 분할함수 Partition함수는 아래와 같습니다.

int Partition(A[],n)
    {
      Left = 1;Right = n-1;
      while(Left < Right){
        while(Left < n && A[Left] < A[0])) Left++; //오른쪽으로 진행하면서 피벗A[0]보다 큰 값의 위치를 찾음
        while(Right > 0 && A[Right] >= A[0])) Right--; //왼쪽으로 진행하면서 피벗A[0]보다 작은값의 위치를 찾음
        if(Left < Right) 
          A[Left]와 A[Right]의 위치 교환
        else
          피벗 A[0]와 A[Right]의 위치 교환 // 피벗과의 위치 교환 후 while문 종료
      }
      retun Right;
    }

 

2) 성능과 특징

분할함수가 진행되면서 반복안에서 각 데이터는 피벗과 1회 또는 2회정도만 비교합니다. 따라서 분할함수의 성능은 Θ(n)이 됩니다. 즉 데이터의 개수에 비례합니다.

 

이때 퀵정렬의 수행시간은 분할되는 두 부분배열의 크기에 따라 달라집니다.

1] 배열이 항상 0:n-1 이나 n-1:0으로 분할되는 경우 → 최악의 경우

피벗이 항상 부분배열의 최소값 또는 최대값이 되는 경우입니다. 따라서 입력데이터가 정렬되어있으며 피벗을 배열의 첫번째 원소로 정한 경우입니다.

 

이를 점화식으로 표현하면 다음과 같습니다. T(n) = T(n-1)+T(0)+ Θ(n)이 되며 결국 T(n) = O(n^2)이 됩니다.

 

2] 배열이 항상 절반으로 분할되는 경우 → 최선의 경우

이 경우는 피벗을 중심으로 항상 동일한 크기의 두 부분 배열로 분할되는 경우입니다. 즉 피벗이 항상 배열의 중간값이 되는 경우라고 할 수 있습니다.

 

이를 점화식으로 표현하면 다음과 같습니다. T(n) = T(n/2)+T(n/2) + Θ(n) = 2T(n/2) + Θ(n)이며 결국 T(n) = O(nlogn)이 됩니다.

 

이를 통해 퀵정렬의 평균 수행시간을 구해보면 T(n) = O(nlogn)이 됩니다.

 

그리고 퀵정렬은 제자리정렬 알고리즘이면서 안정적이지 않은 정렬 알고리즘입니다.

 

그런데 퀵정렬의 특징으로는 피벗선택만 제대로 한다면 평균 수행시간을 보장합니다. 즉, 피벗을 배열의 첫번째 원소로 지정하면서 배열이 정렬된 경우만 아니면 됩니다. 그런데 입력배열이 정렬되어있는지 안되어있는지는 알 수 없기 때문에 피벗을 랜덤하게 지정하면 됩니다.

 

일반적으로 배열의 임의의 값을 선택한 후 배열의 첫번째 원소와 교환한 후 정렬을 수행합니다.

 

또 다른 특징으로는 분할정복 방법이 적용된 알고리즘이기 때문에 순환 알고리즘이 되고 순환알고리즘은 점화식으로 표현할 수 있습니다. 

6. 합병정렬

주어진 배열을 동일한 크기의 두 부분배열로 분할하고 각 부분배열에 순환적으로 합병정렬을 적용하여 정렬시킨 후 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 방식입니다.

 

1) 알고리즘

MergeSort(A[],n)
  {
   if(n>1){
     Mid = |n /2|;
     B[0,..,Mid-1] = MergerSort(A[0,..,Mid-1],Mid);
     C[0,..,n-Mid-1] = MergerSort(A[Mid,..,n-1],n-Mid]);
      A[0,..,n-1] = Merge(B[0,..,Mid-1],C[0,..,n-Mid-1],Mid,n-Mid);
   
   } 
     return A
  }

 

알고리즘은 2개가 남을때까지 전부 절반으로 분할합니다. 그리고 분할된 두 수를 비교한 후 정렬합니다. 그 후 역순으로 올라가면서 4,8,16... 합쳐가면서 데이터를 비교하면서 정렬합니다.

 

이때 합병함수 Merge()의 알고리즘은 아래와 같습니다.

 

Merge(B[],C[],n,m)
  {
    i=j=k=0;
    while(i<n && j<m)
      if(B[i]<=C[j])
        A[k++]=B[i++];
      else
        A[k++]=C[j++];
    for(;i<n;i++) A[k++]=B[i];
    for(;j<m;j++) A[k++]=C[j];
    return A[0,..,n+m-1];

  }

 

합병함수를 보면 입력배열B와 C를 비교하면서 정렬하면서 배열A에 하나씩 넣습니다.

 

두 입력배열 B와 C의 비교횟수는 n/2 ~ n-1번까지입니다. 따라서 합병함수의 수행시간은 Θ(n)이 됩니다.

 

이를 통해 합병정렬을 점화식으로 표현하면 다음과 같습니다. T(n) = T(n/2)+T(n/2) + Θ(n) = 2T(n/2) + Θ(n)이며 결국 성능은 T(n) = O(nlogn)이 됩니다. 

 

이러한 합병정렬은 안정적인 정렬 알고리즘이지만 제자리정렬 알고리즘은 아닙니다. 왜냐하면 입력크기 n이 증가함에 따라 입력배열 B와 C의 크기도 같이 커지기되어 추가적인 공간을 요구하기 때문입니다.

 

또한 합병정렬도 퀵정렬과 마찬가지로 분할정복 방법이 적용된 알고리즘입니다. 

7. 힙 정렬

힙 정렬은 힙이라는 자료구조의 장점을 활용한 정렬입니다.

 

힙(heap)이란?

각 노드의 값이 자신의 자식노드의 값보다 크거나 같은 완전 이진트리를 최대힙이라고 합니다.

각 노드의 값이 자신의 자식노드의 값보다 작거나 같은 완전 이진트리는 최소힙이라고 합니다.

일반적으로 오름차순으로 정렬할때는 최대힙을 사용하며 내림차순으로 정렬할때에는 최소힙을 사용합니다.

 

힙을 사용할때는 트리를 노드 순서에 따라 1차원 배열로 변환하여 사용합니다. 왜냐하면 인덱스를 조절하여 부모노드와 자식 노드를 찾을 수 있기 때문입니다.

1) 힙의 재구성 과정

힙의 첫번째 장점은 임의의 값을 삽입할 수 있습니다. 먼저 마지막 노드에 주어진 임의의 값을 넣습니다. 1차원 배열이라면 마지막에 넣는 것입니다. 이때 임의의 값이 해당 노드의 부모노드보다 크다면 자리를 교체합니다. 이것을 힙의 조건이 성립될 때까지 반복합니다.

 

힙의 두번째 장점은 최대값을 삭제할 수 있다는 것입니다.

힙에서는 무조건 루트 노드가 최대값이 됩니다. 이를 삭제하기 위해서 루트노드와 마지막값을 교환합니다. 교환한 후 새로 구성된 루트노드와 자식노드보다 작다면 자식 노드 중 큰값과 교환합니다. 이것을 반복하여 힙의 조건을 성립시킵니다.

 

2) 힙 정렬 처리과정 순서도

 

3) 힙정렬 알고리즘

HeapSort(A[],n)
  {
    // 단계1 
    for(i=0;i<n;i++){
      par = (i-1)/2;
      while(par>=0 && A[par]<A[i]){
        A[par]와 A[i] 교환;
        i=par;
        par = (i-1)/2;
      }
    }
    // 단계2
    for(i=n-1;i>=0;i--){
      최대값A[0]와 마지막 노드 A[i]의 교환;
      cur = 0; lch=1; rch=2;
      do{ //힙의 재구성
        if(rch <i && A[lch]<A[rch]) lch = rch;
        if(A[lch] > A[cur]){
          A[cur]과 A[lch]의 교환;
          cur = lch;
          lch = cur*2+1;
          rch = cur*2+2;
        }
        else lch = i;
      }while(lch<i)
    }
    return A
  }

 

4) 힙 정렬 진행단계

 

힙정렬의 첫번째 단계는 주어진 1차원 배열을 힙으로 변환하는 것입니다. 이 방법에는 두가지가 있습니다. 

 

첫번째 방법은 주어진 입력배열의 각 원소를 힙에 삽입하는 과정을 반복하는 것입니다.

 

예제를 통해 자세히 알아보겠습니다.

 

입력배열을 [60,20,70,10,80,30,50,40]이라고 가정해 보겠습니다. 

 

1: 결과 배열의 1번째에 60을 부여합니다. → 결과 배열은 [60]이 됩니다.

2: 결과 배열의 2번째에 20을 부여합니다. 이때 20은 60보다 작기때문에 교환은 없습니다.

     → 결과 배열은 [60,20]이 됩니다.

3: 결과 배열의 3번째에 70을 부여합니다. 이때 70은 60보다 크기때문에 서로 교환합니다.

     → 결과 배열은 [70,20,60]이 됩니다. 

4: 결과 배열의 4번째에 10을 부여합니다. 이때 10은 20보다 작기 때문에 교환은 없습니다.

     → 결과 배열은 [70,20,60,10]이 됩니다.

5: 결과 배열의 5번째에 80을 부여합니다. 이때 80은 20보다 크기때문에 서로 교환합니다.

     → 결과 배열은 [70,80,60,10,20]이 됩니다. 그런데 80은 70보다 크기 때문에 한번 더 교환합니다.

     → 결과 배열은 [80,70,60,10,20]이 됩니다.

6: 결과 배열의 6번째에 30을 부여합니다. 이때 30은 60보다 작기 때문에 교환은 없습니다.

     → 결과 배열은 [80,70,60,10,20,30]이 됩니다.

7: 결과 배열의 7번째에 50을 부여합니다. 이때 50은 60보다 작기 때문에 교환은 없습니다.

     → 결과 배열은 [80,70,60,10,20,30,50]이 됩니다.

8: 결과 배열의 8번째에 40을 부여합니다. 이때 40은 10보다 크기 때문에 서로 교환합니다.

     → 결과 배열은[80,70,60,40,20,30,50,10]이 됩니다. 

     → 위의 결과배열은 힙이 됩니다.

 

 

두번째 방법은 주어진 입력배열을 우선 완전 이진트리로 만든 후 각 노드에 대해 아래에서 위로 그리고 오른쪽에서 왼쪽으로 진행하면서 해당 노드의 아랫부분이 힙의 조건을 만족할 수 있도록 트리를 따라 올라가면서 자신의 자손노드들과의 위치교환을 계속해 나가는 방법입니다.

 

예제를 통해 자세히 알아보겠습니다.

 

첫번째 방법과 동일하게 입력배열이 주어졌을 때 아래 그림처럼 완전 이진트리로 만듭니다.

 

40→50 →30 → ...으로 진행하면서 자식노드와 값을 비교하여 힙을 만들어 나갑니다.

먼저 80까지는 자식노드가 없기때문에 확인할 값이 없습니다. 그다음부터 10과 40을 비교하여 부모노드인 10이 더 작으므로 40과 교환합니다. 20과도 비교해야겠지만 순차적으로 올라가면서 비교하기 때문에 지금은 비교하지 않습니다. 그 다음 70은 30과 50보다 크므로 변화가 없고 20에 이르렀을때 자식노드인 40,80과 비교하여 80이 더 크므로 80과 20을 교환합니다. 마지막으로 60에 이르렀을때 부모노드인 60보다 자식노드인 80이 더 크므로 또 교환합니다. 이렇게해서 힙을 구성할 수 있습니다.

 

힙 정렬의 두번째 단계는 최대값을 삭제하는 것입니다. (실제로 삭제하는 것은 아닙니다.)

위의 예에서 구축된 힙의 루트노드가 최대값이므로 80과 마지막 노드인 10과 교환합니다. 

그 후 새로운 루트노드부터 차례로 진행하면서 힙이 재구성될수있도록 교환합니다.

새롭게 구성된 힙의 루트노드는 70이 될 것입니다. 그러면 또 70과 마지막값인 10과 교환한 후 힙을 재구성합니다.

이것을 반복하면 최종 결과는 [10,20,30,40,50,60,70,80]이 될 것입니다.

5) 성능과 특징

힙정렬은 최선, 최악, 평균수행시간은 모두 O(nlogn)이 됩니다.

왜냐하면 중첩 반복이긴 하지만, 바깥은 입력크기 n에 비례하고 안쪽은 완전이진트리의 높이 logn에 비례하기 때문에 성능은 nlogn이 됩니다.

 

그리고 힙정렬은 안정적이지 않은 정렬 알고리즘입니다. 그리고 제자리 정렬 알고리즘입니다.