 |
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()배열에 저장합니다. 위의 예에선 다음과 같은 결과를 보여줄 겁니다.
MaxStringLen(1)
|
MaxStringLen(2)
|
MaxStringLen(3)
|
MaxStringLen(4)
|
3
|
2
|
1
|
1
|
'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)값을 열의 최대값만큼 맞추어 붙여줍니다. 따라서 위의 예에 따른 결과는 다음과 같을 겁니다.
a00
|
b0
|
d
|
1
|
aa0
|
b0
|
e
|
2
|
aaa
|
b0
|
e
|
3
|
a00
|
bb
|
d
|
4
|
aa0
|
bb
|
e
|
5
|
aaa
|
bb
|
e
|
6
|
a00
|
a0
|
d
|
7
|
aa0
|
a0
|
d
|
8
|
aaa
|
a0
|
d
|
9
|
(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()의 값은 다음과 같을 겁니다.
SingleList(1)
|
a00b0d1
|
SingleList(2)
|
aa0b0e2
|
SingleList(3)
|
aaab0e3
|
SingleList(4)
|
a00bbd4
|
SingleList(5)
|
aa0bbe5
|
SingleList(6)
|
aaabbe6
|
SingleList(7)
|
a00a0d7
|
SingleList(8)
|
aa0a0d8
|
SingleList(9)
|
aaaa0d9
|
'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
|
OfficeTutor 365