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

데이터를 정렬하기 위해 임의의 두 숫자 배열을 가져와서 작은 수를 선택하여 1개의 배열을 만드는 함수를 만들어두었습니다. 이번에는 이 함수를 이용하여 실제 데이터를 정렬하고자 합니다.

정렬함수를 만들기에 앞서, 다음과 같이 모듈 제일 첫줄에 사용자 정의 변수를 선언해둡니다.

Public Type typeArray
  Y() As Double
End Type

typeArray라는 변수는 그 안에 크기가 지정되지 않은 Double형 배열입니다. 이렇게 해두면 숫자나 문자열같은 한 개의 데이터가 아니라, 한 개의 변수 안에 배열을 통째로 넣어두겠다는 말입니다.

이제 본격적으로 정렬 함수를 만들어보겠습니다. 또한, 중간 중간에 코멘트를 달아서 설명을 드리겠습니다.

--------------------------------------------------

Function GetSorted(iData() As Double, Optional iGetOrder As Boolean = False, Optional iIncrease As Boolean = True, Optional iDelDuplicate As Boolean = False) As Double()

  Dim tD1() As typeArray, tD2() As typeArray, tN As Long, tV() As Double, tOdd As Boolean, tC As Long, tSN As Long, tFN As Long
  Dim i As Long, j As Long, n As Long

  '입력받는 데이터는 1차원 배열이며, tD1, tD2는 지정해두지 않았습니다. tD1, tD2는 또한 배열인데, 그 안의 데이터는 앞에서 선언한 배열이 들어가 있습니다. 예를 들어, tD1(2).Y이라고 한다면, 2번째 tD1 변수에 입력된 숫자 배열을 의미하고,  tD1(2).Y(3)이라고 한다면, 2번째 tD1에 입력된 배열의 3번째 데이터라는 것이지요. 그 외에 함수에 사용될 변수들을 선언해둡니다.

  tSN = LBound(iData): tFN = UBound(iData)
  tN = UBound(iData) - LBound(iData) + 1  

  'tN에는 입력받은 데이터의 크기를 넣어둡니다. 1차원 배열을 입력받을 것이므로, 첫번째와 마지막 index의 차이에서 1을 더하면, 입력받은 데이터가 반드시 0이나 1로 시작하지 않더라도 그 크기를 알 수 있습니다. 또한, 시작 index와 마지막 index를 미리 변수에 선언해두면 메모리는 몇 바이트 정도 더 쓰겠지만, 코드 길이는 짧아지는 장점이 있습니다.

  '만약, 한 줄에 들어가는 코드가 짧고, 행 구분이 필요없다면 콜론( : )으로 연결해두면 굳이 2줄 이상으로 쓸 필요없이 한 줄로 표현이 가능합니다.

  If iGetOrder Then
    tC = 2
    ReDim tD1(1 To tN)
    For i = tSN To tFN
      n = i + 1 - tSN: ReDim tD1(n).Y(1 To 1, 1 To 2)

      tD1(n).Y(1, 1) = iData(i): tD1(n).Y(1, 2) = i
    Next
  Else
    tC = 1
    ReDim tD1(1 To tN)
    For i = tSN To tFN
      n = i + 1 - tSN: ReDim tD1(n).Y(1 To 1, 1 To 1): tD1(n).Y(1, 1) = iData(i)
    Next
  End If
  'iGetOrder는 입력받은 숫자 배열의 순서(Order)를 찾아낼 것인지, 아니면 크기순으로 새로 정렬된 데이터 배열을 구할 것인지를 지정합니다. 기본값은 배열을 크기순으로 재정렬하는 것이므로 False로 두었습니다.

  '만약, iGetOrder가 True이면, 입력받은 데이터와 함께 각 데이터의 현재 순서를 입력해주고, False이면 입력받은 데이터만 tD1에 대입해줍니다.

  '최초의 tD1은 입력받은 데이터(iData)의 갯수와 같고, 그 안에는 크기가 1인 배열이 입력되어있습니다. 즉, 모든 데이터를 크기 1짜리 배열로 바꿔둔 것입니다.

  If tN = 1 Then tD2 = tD1
  While UBound(tD1) > 1
    tOdd = (UBound(tD1) Mod 2 = 1)
    tN = Int(UBound(tD1) / 2): If tOdd Then tN = tN + 1
    ReDim tD2(1 To tN)
    For i = 2 To UBound(tD1) Step 2: tD2(i / 2).Y = SortStep(tD1(i - 1).Y, tD1(i).Y): Next
    If tOdd Then tD2(tN).Y = tD1(UBound(tD1)).Y
    tD1 = tD2
  Wend
  '만약 입력받은 데이터의 크기가 1이라면 정렬할 필요가 없습니다.

  'tD1의 크기가 2개 이상이라면, 2개의 데이터, 즉, tD1(2n-1)의 데이터와 tD1(2n)의 데이터를 미리 만들어둔 2개의 배열 데이터를 합치는 함수에 넣어서 합쳐서 tD2에 저장해둡니다. 만약, tD1이 짝수개라면 좋겠지만, 홀수개라면 마지막에 1개가 남게 되겠지요. 마지막에 남은 배열은 정렬없이 그냥 tD2의 마지막에 대입해둡니다. 이렇게 되면, 2개의 데이터를 병합한 배열은 크기가 크지만, 마지막에 남은 배열은 크기가 작습니다. SortStep 함수에서 입력받는 2개의 데이터 크기가 서로 다른 경우에도 합칠 수 있도록 했던 이유가 이러한 이유에서입니다.

  '한번의 병합 작업이 완료되면, tD2의 배열 데이터를 tD1으로 다시 옮겨옵니다. 만약, tD1의 크기를 확인했을 때, 1이라면 작업을 완료합니다. 이제 tD1의 크기는 1이고, tD1(1)에 저장된 Y 데이터는 입력받은 데이터와 같은 크기를 가지게 되며, 오름차순 정렬을 마친 것이지요.

  '만약, iGetOrder가 True였다면, 어떻게 되었을까요? 처음 입력받은 iData가 정렬되면서, 앞에서부터 1, 2, 3,.. 으로 붙여주었던 인덱스들이 숫자가 정렬되면서 함께 이동합니다. 이러한 기능을 어디다 써야할지는 사용자가 선택하면 되겠습니다.

  
  ReDim tD1(1).Y(tSN To tFN, 1 To tC)
  If iIncrease Then
    For i = tSN To tFN
      n = i - tSN + 1
      For j = 1 To tC
        tD1(1).Y(i, j) = tD2(1).Y(n, j)
      Next
    Next
  Else
    For i = tSN To tFN
      n = tFN - i + 1
      For j = 1 To tC
        tD1(1).Y(i, j) = tD2(1).Y(n, j)
      Next
    Next
  End If

  '만약, 오름차순이 아니라 내림차순으로 정렬하고자 한다면, 숫자 배열을 거꾸로 출력해주면 되겠지요. 숫자 배열을 반대로 출력하느라 또 한번의 작업을 해야하는 것이지만, 대신 여러개의 프로시저를 짜거나, 코드가 복잡해지지는 않습니다. 이러한 작업시간마저도 아깝다면, SortStep과 현재의 함수에서 처음부터 오름차순으로 정렬할지, 내림차순으로 정렬할지 판단해서 코드를 추가해주면 됩니다.

  If iDelDuplicate Then
    n = tSN: ReDim Preserve tV(tSN To n): tV(n) = tD1(1).Y(1, tC)
    For i = tSN + 1 To tFN
      If Not (tD1(1).Y(i - 1, 1) = tD1(1).Y(i, 1)) Then
        n = n + 1: ReDim Preserve tV(tSN To n): tV(n) = tD1(1).Y(i, tC)
      End If
    Next
  Else
    ReDim Preserve tV(tSN To tFN)
    For i = tSN To tFN
      tV(i) = tD1(1).Y(i, tC)
    Next
  End If

  '중복된 데이터는 삭제하고 싶다면, 위와 같이 서로 중복된 데이터는 삭제해주면 됩니다. 불필요한 기능이라면 이 부분은 삭제하시면 됩니다. 입력받은 데이터가 1차원 데이터이기 때문에 출력되는 데이터도 1차원으로 변환해줍니다. 또한, 입력받은 데이터의 시작과 끝 index가 0이나 1로 시작되지 않을 수 있으므로, 인덱스도 원래 입력받은 인덱스대로 바꿔줍니다.

  '마지막으로 정렬된 데이터를 반환해주고 함수를 끝냅니다.
  GetSorted = tV
  Erase tD1, tD2, tV
End Function

--------------------------------------------------

아래의 함수 GetSorted2는 통상의 교재에서 소개하는 정렬 알고리즘입니다. 2개의 데이터를 비교해서 작은 데이터를 앞으로 옮기는 것을 반복하는 방법입니다. 특별한 기능을 넣지 않은 이유도 있지만, 앞에서와 동일한 기능을 갖도록 하더라도 코드는 상대적으로 간결합니다.

Function GetSorted2(iData() As Double) As Double()
  tData = iData
  tSN = LBound(tData): tFN = UBound(tData)
  For i = tSN To tFN
    For j = i + 1 To tFN
      If tData(i) > tData(j) Then tVal = tData(i): tData(i) = tData(j): tData(j) = tVal
    Next
  Next
  GetSorted2 = tData
  Erase tData
End Function

위에서 코딩해둔 2개의 정렬함수의 속도차이를 비교해보실 수 있도록 아래와 같은 코드를 넣고 실행해보시기 바랍니다.

Function RandArray(iNum As Long) As Double()

  Dim i As Long, tData() As Double, tVec() As Double

  ReDim tData(1 To iNum)

  ReDim tVec(1 To iNum, 1 To 1)

  For i = 1 To iNum

    tData(i) = Rnd() * 100

    tVec(i, 1) = tData(i)

  Next

  ActiveSheet.Range(Cells(1, 1), Cells(iNum, 1)).Value = tVec

  RandArray = tData

  Erase tData, tVec

End Function

위의 함수는 현재 워크시트의 1열에 원하는 갯수만큼 난수를 발생시켜 입력합니다.

Sub Test1()
  Dim tData() As Double, tSorted(), n As Long
  n = 50000
  tData = RandArray(n)
  MsgBox "정렬 시작", vbInformation, "확인"
  tData = GetSorted(tData, False, True, False)
  ReDim tSorted(1 To n, 1 To 1)
  For i = 1 To n
    tSorted(i, 1) = tData(i)
  Next
  ActiveSheet.Range(Cells(1, 3), Cells(n, 3)).Value = tSorted
End Sub

Sub Test2()
  Dim tData() As Double, tSorted(), n As Long
  n = 50000
  tData = RandArray(n)
  MsgBox "정렬 시작", vbInformation, "확인"
  tData = GetSorted2(tData)
  ReDim tSorted(1 To n, 1 To 1)
  For i = 1 To n
    tSorted(i, 1) = tData(i)
  Next
  ActiveSheet.Range(Cells(1, 4), Cells(n, 4)).Value = tSorted
End Sub

Test1과 Test2는 각각 5만개의 난수 데이터를 생성하고, 서로 다른 정렬함수로 정렬하는 프로시저입니다. 만약, 오래된 사무용 PC에서 작업하신다면, 2만개 정도로 줄여도 됩니다. 혹은 PC 성능이 너무 좋아서 두 프로시저의 속도차이를 못느끼신다면, 10만개 혹은 100만개의 데이터를 생성하도록 해서 비교해보시면 되겠습니다.

위의 두 프로시저 비교를 마치고 나면, 엑셀에 내장된 정렬 기능과 Test1의 속도를 비교해보시면 좋을 것 같습니다. 아마, 속도차이를 크게 느끼지 못하실 것입니다. 대부분의 상용 소프트웨어나 파이썬 등에서 사용하는 정렬 알고리즘과 큰 차이가 나지는 않을 것입니다.

이상 데이터 정렬 알고리즘을 하나 소개해드렸습니다.