Module 2. 데이터 정렬(Sorting)하기 (1)

엑셀에는 기본적으로 값을 필터링하고 정렬하는 기본 기능이 포함되어 있어서, 매크로를 이용하여 굳이 데이터를 정렬하는 알고리즘이 필요하지 않을 수 있습니다.

단순히 현재 워크시트에 있는 데이터를 정렬만 한다면, VBA 편집기에서 Sheet명.Sort 를 적절하게 사용하면 됩니다.

그러나, 여러 개의 데이터셋을 불러와서, 이 값들에 대해 정렬하고, 원하는 계산을 수행한 후 다시 결과를 출력해야하는 상황이라면 내장된 정렬 기능만으로는 처리하기 어려운 일이 생길 수 있습니다.

어떠한 프로그래밍 언어를 배우시든, For 문, If 문의 활용 예제로서 데이터 정렬을 한번쯤은 해보셨을 수 있으실텐데, 가장 간단한 알고리즘이 아래와 같이 배열에 있는 두 데이터를 일일이 비교해서, 앞의 숫자가 크면 뒤의 숫자와 교체하는 방식으로 정렬하는 것으로 배울 것입니다.

문제는 몇개 안되는 숫자 배열이라면 그럭저럭 쓸만하지만, 갯수가 커지면 연산횟수가 급격히 증가해서 속도가 느려지는 문제가 있습니다. Wikipedia에 설명된 정렬 알고리즘 (https://en.wikipedia.org/wiki/Sorting_algorithm)을 참고하시면 좋을 것 같습니다. 앞에서 설명드린 알고리즘은 위키백과에서 설명한 Selection sort에 해당합니다. 잘 정렬된 배열이든, 무작위로 배열된 경우이든 상관없이 정렬에 필요한 연산 횟수가 가장 많은 상태임을 알 수 있으며, 연산 시간이 배열에 포함된 데이터 갯수의 제곱에 비례하는 것을 알 수 있습니다. 즉 100개의 데이터라면 100^2=1만번의 비교 연산이 필요하지만, 만약 10만개의 데이터가 있다면 100억 회의 연산이 필요하게 됩니다. 만약, 1초에 1억회의 연산을 한다하더라도 100초가 걸리고, 그보다 계산 속도가 느리다면, 더욱 오래 걸리게 될테니... 아무리 좋은 PC라도 인내심의 한계에 도달하게 되는 것이지요. 10만개의 데이터라면 요즘에는 그리 큰 데이터가 아닌데도 말입니다.

한편, 엑셀에 내장된 정렬 기능은 100만개의 데이터라 하더라도 단 몇초도 걸리지 않고 정렬하는 것을 알 수 있습니다. 도대체 어떤 방법을 쓴 것일까요? 위키백과에서 Worst case일지라도 n log n 회 연산만 필요한 알고리즘을 쓰게 되면 연산횟수가 급격하게 줄어듭니다. 대략 10만개의 데이터라도 10만 x 5회, 즉 50만회 연산만 필요하게 되니, 1초도 걸리지 않고 작업이 완료되는 것입니다. (정확하게는 이보다 조금더 많은 연산이 필요하지만 그다지 차이는 없습니다.) 다만, 이러한 알고리즘은 메모리를 조금 더쓰게 되거나, 알고리즘이 안정적이지 않다는 문제가 있는데.. 안정적이면서도 메모리를 적게 쓰는 경우에는... 프로그래밍하기엔 조금 복잡하다는 단점이 있습니다.

이번에 설명드릴 정렬 매크로는 Merge sort 방법을 구현해보도록 하겠습니다. 개략적인 개념은 링크의 위키백과의 그림 부분을 참고하시기 바랍니다. 간단히 개념을 말씀드리면, 데이터 배열을 크기가 1인 배열로 나눠줍니다. 나눠진 배열을 2개씩 쌍을 지어 크기별로 병합하여 크기가 2인 배열을 만듭니다. 다시 크기가 2인 배열을 크기 순으로 병합하여 크기가 4인 배열을 만듭니다. 이렇게 반복하면 8, 16, 32,...의 크기를 갖는 배열로 병합되면서 배열이 완료되는 것이지요. 계속 2배씩 배열의 크기가 커지니 반복 횟수는 생각보다 많지는 않습니다.

이러한 매크로를 만들기 위해서, 2개의 숫자 배열을 입력하면, 크기 순으로 하나의 배열로 병합하는 함수를 먼저 만들어보도록 하겠습니다.

Function SortStep(iD1() As Double, iD2() As Double) As Double()
  Dim i As Long, j As Long, k As Long, l As Long, n As Long

  Dim tSN1 As Long, tFN1 As Long, tSN2 As Long, tFN2 As Long

  Dim tD() As Double, tN As Long, tC1 As Long, tC2 As Long
  tSN1 = LBound(iD1, 1): tFN1 = UBound(iD1, 1)

  tSN2 = LBound(iD2, 1): tFN2 = UBound(iD2, 1)
  tC1 = LBound(iD1, 2): tC2 = UBound(iD1, 2)
  tN = tFN1 - tSN1 + tFN2 - tSN2 + 2
  ReDim tD(1 To tN, tC1 To tC2)
  j = tSN2
  n = 0
  For i = tSN1 To tFN1
    n = n + 1
    If iD1(i, tC1) < iD2(j, tC1) Then
      For k = tC1 To tC2: tD(n, k) = iD1(i, k): Next
    ElseIf iD1(i, tC1) = iD2(j, tC1) Then
      n = n + 1
      For k = tC1 To tC2: tD(n - 1, k) = iD1(i, k): tD(n, k) = iD2(j, k): Next
      j = j + 1
      If j > tFN2 Then i = i + 1: Exit For
    Else
      For k = tC1 To tC2: tD(n, k) = iD2(j, k): Next
      j = j + 1: If j > tFN2 Then Exit For
      i = i - 1
    End If
  Next
  If i <= tFN1 Then
    For k = i To tFN1
      n = n + 1
      For l = tC1 To tC2: tD(n, l) = iD1(k, l): Next
    Next
  End If
  If j <= tFN2 Then
    For k = j To tFN2
      n = n + 1
      For l = tC1 To tC2: tD(n, l) = iD2(k, l): Next
    Next
  End If
  SortStep = tD
  Erase tD
End Function

입력되는 배열이 0부터 시작할지, 1부터 시작할지.. 아니면 다른 index에서 시작할지 모르니, 배열의 시작과 끝 index를 먼저 확인하고, 병합해서 데이터를 입력할 배열(tD)의 크기를 지정해줍니다.

병합할 데이터 배열 tD가 지정되었다면, 입력된 두 배열 iD1, iD2에서 앞에 있는 숫자를 하나씩 꺼내어 비교하고 작은 숫자를 먼저 tD에 차례로 입력합니다. 이렇게 iD1과 iD2에 있는 모든 숫자를 다 tD 배열에 입력했다면, 이 배열을 결과값으로 반환해줍니다.

반환된 tD는 이미 작은 숫자에서 큰 숫자로 오름차순 정렬되어 있기 때문에, 병합된 배열 2개를 다시 위의 함수에 입력하여, 앞에 숫자부터 차례로 꺼내면서 재병합하는 과정을 거칩니다.

이렇게 되면 항상 반환된 배열의 크기는 1, 2, 4, 8, ... 과 같이 2배씩 증가할 것 같지만, 위의 함수에서는 입력되는 배열의 크기를 임의로 지정해두었습니다. 이것은 원래 정렬하려는 배열의 크기가 2^n개가 아니라면, 2개씩 비교하여 병합하는 과정에서 마지막 몇개의 숫자가 남아서 정렬되지 못할 수 있기 때문에 입력되는 데이터가 반드시 2^n개가 아닐 수 있고, 반환되는 배열 역시 마찬가지이기 때문에 입력 또는 반환되는 배열의 크기를 지정하지 않고, 임의의 크기를 갖는 배열을 입력받도록 해둔 것입니다.

그런데, 위의 함수에서 입력 및 반환되는 배열이 1차원이 아니고 2차원 배열이지요? 여기서 소개해드리는 매크로는 단순히 숫자 배열하는 것 뿐만 아니라, 배열을 그대로 유지하고 그 숫자의 크기 순서(Rank)를 찾아내는 방법을 조합할 목적이기 때문입니다. 예를 들어, (5,3,7,2,9)라는 배열이 있다면 Rank 배열은 각 숫자의 순서를 나타내는 (3,2,4,1,5)를 출력하는 것이지요. 이렇게 어떤 배열의 순서를 알고 있다면, 배열을 재정렬함으로써 순서를 흐트리지 않고도 이미 indexing이 되어 있기 때문에 원하는 순서의 숫자를 빠르게 찾아낼 수 있습니다. 즉, 앞의 배열에서 크기순으로 4번째인 숫자를 찾기 위해 Rank 배열에서 4를 찾아서, 여기에 해당하는 원래 데이터 배열의 같은 위치에 있는 7을 출력하게 됩니다. 아무튼... 이러한 기능의 활용 부분에 대해서는 다음에 소개해드리도록 하겠습니다. 만약 이러한 indexing 작업이 불필요하다고 생각되시는 분은 1차원 배열로 적당히 바꾸시면 됩니다만, 바꾸지 않더라도 연산 속도에는 별로 영향을 주지는 않습니다.

위와 같이 원하는 목적을 갖는 전체 매크로를 프로그래밍하기 전에, 전체적인 흐름에서 최소 반복 단위를 먼저 구분하여 함수로 만들고, 이 함수를 다시 조합하여 원하는 기능을 갖는 매크로로 만들어가면 비록 함수의 갯수, 종류는 많아질 수 있지만, 간결하고 짧게 매크로를 만들 수 있습니다. 다만, 전체 기능을 소단위의 기능으로 자르고 구분하는 것이 쉽지 않기도 하고, 간혹 전문적인 수학 지식이 필요한 경우도 있어서 문제 해결을 위해 많은 자료들을 참고해야하기도 합니다.