16. 정렬 세 번째 이야기

안녕하세요, 오늘은 정렬에 관한 마지막 시간으로 Dave Steppan의 정렬함수를 설명해드리고자 합니다. 지난 시간에 이것을 가지고 폼을 만들어 4개 이상의 키를 효과적으로 정렬하는 것을 보여드렸습니다. 

프로시져는 2개입니다. 하나는 MultiColumnSort()함수이고, 나머지 하나는 RankSort()프로시져입니다. 그리고 MultiColumnSort()가 RankSort()를 호출합니다. 알고리즘의 대강을 설명드리자면 MultiColumnSort()함수는 정렬할 목록과 정렬순서를 입력받습니다. 그리고 목록내 각 열의 길이를 고정시키고 목록의 각 열을 하나로 합쳐 RankSort()에 넘겨줍니다. 그리고 RankSort()함수는 하나의 열로 합쳐진 벡터를 받아 단순히 정렬합니다. 그걸로 끝입니다.

설명을 위해 다음과 같은 데이터를 정렬한다고 가정하겠습니다.

Function MultiColumnSort(UnSortedArray As Variant, SortOrder As Integer)
     Dim OriginalArray As Variant
     Dim SortedArray As Variant
     Dim SingleList As Variant
     Dim MaxStringLen As Variant

     'Make a copy of the unsorted array
     OriginalArray = UnSortedArray
정렬되지 않은 원본을 OriginalArray에 복사합니다. 

     'For loop bounds...
     NumRows = UBound(UnSortedArray, 1)
행의 개수를 알아냅니다. 위의 예에서는 9가 됩니다.
     NumCols = UBound(UnSortedArray, 2)
열의 개수를 알아냅니다. 위의 예에선 4가 됩니다.
UBound()함수와 LBound()함수는 배열의 상위인덱스 값과 하위인덱스 값을 알려줍니다. 그런데 배열이 1차원 이상이면 배열명 다음에 조사할 차원을 지정합니다. 

      ReDim SingleList(1 To NumRows)
정렬할 목록을가질 SingleList()배열과 각 열에서 최고 길이(문자열로 생각했을때)를 가진 값을 저장할 MaxStringLen()배열을 행과 열의 수만큼 배열의 크기를 지정합니다. 

     'Find max length string in each column
     For j = 1 To NumCols

위의 반복문에서는 각 열에서 문자열의 최대길이를 알아내 MaxStringLen()배열에 저장합니다. 위의 예에선 다음과 같은 결과를 보여줄 겁니다. 

     'Make all strings in each column the same length
     'by adding Chr(0) to make the same length
     For j = 1 To NumCols
          For i = 1 To NumRows
               Do While Len(UnSortedArray(i, j)) < MaxStringLen(j)
                    UnSortedArray(i, j) = UnSortedArray(i, j) & Chr(0)
               Loop
          Next
     Next

다시 정렬되지 않은 목록을 일일이 반복하면서 각 배열요소의 길이를 그 열의 최대문자열 길이에 맞춰 Chr(0)값으로 채웁니다. 이것은 정렬을 원할하게 하기 위한 것입니다. 예를 들어 순서대로 번호를 붙여 파일을 만들다보면 탐색기에서 파일이름으로 정렬해도 파일의 순서가 엉터리로 정렬된 것을 볼 수 있습니다. 

가령 1.xls, 2.xls, 3.xls, 4.xls, 5.xls, 6.xls, 7.xls, 8.xls, 9.xls, 10.xls, 11.xls, 12.xls, 13.xls, 14.xls, 15.xls, 16.xls, 17.xls, 18.xls, 19.xls, 20.xls, 21.xls, 22.xls 등등의 파일이 있는 경우 이름순서로 정렬하면 1.xls, 10.xls, 11.xls, 12.xls, 13.xls, 14.xls, 15.xls, 16.xls, 17.xls, 18.xls, 19.xls, 2.xls, 20.xls, 21.xls, 22.xls, 3.xls, 4.xls, 5.xls, 6.xls, 7.xls, 8.xls, 9.xls 순서대로 됩니다. 

그래서 이런 현상을 예방하기 위해 01.xls, 02.xls, 03.xls,...등등 10이하의 이름을 갖는 경우 "0"을 붙여 줍니다. 같은 이유로 여기에서도 Chr(0)값을 열의 최대값만큼 맞추어 붙여줍니다. 따라서 위의 예에 따른 결과는 다음과 같을 겁니다.

(Chr(0)값을 0이라고 가정하는 경우)

     'Concatenate strings to make array into a single
      'vector to sort
     For i = 1 To NumRows
          For j = 1 To NumCols
               SingleList(i) = SingleList(i) & UnSortedArray(i, j)
          Next
     Next
일정한 크기로 채워진 각 열의 값을 행마다 모두 합쳐 하나의 데이터로 표시합니다. 이 결과 SingleList()의 값은 다음과 같을 겁니다.

     'Use a traditional single array sorting algorithm
     Call RankSort(SingleList, SortOrder, RankList)
정렬하는 프로시져를 호출합니다. 정렬된 결과는 RankList()에 저장됩니다.

     ReDim SortedArray(1 To NumRows, 1 To NumCols)
정렬된 목록을 저장할 배열의 크기를 정합니다.

     'Translate results back into a sorted array
     For k = 1 To NumRows
          For j = 1 To NumRows
               If k = RankList(j) Then
                    For i = 1 To NumCols
                         SortedArray(k, i) = OriginalArray(j, i)
                    Next
               End If
          Next
    Next
정렬된 결과에 따라 원본을 정렬한 순서대로 옮겨 저장합니다. Sub RankSort() 프로시저의 실행결과 RankList()배열에는 각 행의 순위가 들어갑니다. 그리고 그순위에 맞춰 원본데이터를 정렬된 배열(SortedArray())에 저장합니다.

     'Feed the beast output
     MultiColumnSort = SortedArray

End Function

Sub RankSort()는 실제 정렬을 하는 부분입니다. 저자의 주석('Use a traditional single array sorting algorithm')대로 평범한 알고리즘을 사용한다고 하지만 알고리즘이 그렇듯 따지고 들려니 매우 머리가 어지럽군요. 해석은 안하고 통과하겠습니다(저도 꾀가 나서 ^^;) 
아마 다음 컬럼은 새해에 시작할 것 같습니다. 미리 인사를 드립니다. 즐거운 연말을 보내시고, 새해 복 많이 많으십시오. 꾸벅 

Sub RankSort(IArray, ByVal nOrder As Integer, rankarray)
     Dim Distance
     Dim Size
     Dim Index
     Dim NextElement
     Dim TEMP
     Dim trankarray() As Integer

     ReDim trankarray(LBound(IArray) To UBound(IArray))
     For i = LBound(IArray) To UBound(IArray)
          trankarray(i) = i
     Next

     ASCENDING_ORDER = 1
     DESCENDING_ORDER = -1
     Size = UBound(IArray) - LBound(IArray) + 1
     Distance = 1

     While (Distance <= Size)
          Distance = 2 * Distance
     Wend

     Distance = (Distance / 2) - 1

     While (Distance > 0)
          NextElement = LBound(IArray) + Distance
          While (NextElement <= UBound(IArray))
               Index = NextElement
               Do
                    If Index >= (LBound(IArray) + Distance) Then
                         If nOrder = ASCENDING_ORDER Then
                              If IArray(Index) < IArray(Index - Distance) Then
                                   TEMP = IArray(Index)
                                   IArray(Index) = IArray(Index - Distance)
                                   IArray(Index - Distance) = TEMP
                                   TEMP = trankarray(Index)
                                   trankarray(Index) = trankarray(Index - Distance)
                                   trankarray(Index - Distance) = TEMP
                                   Index = Index - Distance
                                   gIterations = gIterations + 1
                              Else
                                   Exit Do
                              End If
                         ElseIf nOrder = DESCENDING_ORDER Then
                              If IArray(Index) >= IArray(Index - Distance) Then
                                   TEMP = IArray(Index)
                                   Array(Index) = IArray(Index - Distance)
                                   IArray(Index - Distance) = TEMP
                                  TEMP = trankarray(Index)
                                  trankarray(Index) = trankarray(Index - Distance)
                                  trankarray(Index - Distance) = TEMP
                                  Index = Index - Distance
                                  gIterations = gIterations + 1
                             Else
                                  Exit Do
                             End If
                        End If
                   Else
                        Exit Do
                   End If
              Loop
              NextElement = NextElement + 1
              gIterations = gIterations + 1
         Wend
         Distance = (Distance - 1) / 2
         gIterations = gIterations + 1
     Wend

     ReDim rankarray(LBound(IArray) To UBound(IArray))
     For i = LBound(IArray) To UBound(IArray)
          rankarray(trankarray(i)) = i
     Next
End Sub

목차 | 이전 | 다음