 |
14. 정렬
첫 번째 이야기
자료다운로드 : 오튜공구함014.xls
자료다운로드 : 12강
수정내용.txt
안녕하세요 오튜가족 여러분!
오늘부터는 정렬에 관한 내용을 다루고자 합니다. 정렬이 사용자들에게는 간단해 보이지만 사실 얼마나 많은 데이터를 빨리 정렬할 수 있는가의 문제에 이르르면
적잖이 어려운 문제이기도 합니다. 정렬을 하려면 무언가를 서로 비교하고 교환해야 합니다. 비교횟수와 교환횟수가 작으면 작을 수록 좋겠죠.
정렬을 다루기에 앞서 지난 저의 컬럼에서 오류가 있어 수정한 바가 있습니다. 사실 많은 테스트를 해보질 않아서 에러가 난 것인데, 다행히 저의 컬럼을 읽어주시는 몇 분께서 지적을 해주셨습니다. 여지껏 컬럼에 대해 어떤 메일을 보내주신 분들이 없었는데, 여러분의 피드백을 받기 위해 앞으로는 자주 틀려봐야 할 것 같습니다. ^^; 저에게 메일로 이걸 알려주신 분이 수정한 내용도 다시 틀렸다고 하시면서 보내주신 소스코드를 첨부하였습니다.
정렬에 대한 여러 가지 알고리즘(insertion sort, selection sort, bubble sort, quick sort, two-way merge sort, heap sort, radix sort)이 있지만 여기서는 비교적 빠른 정렬에 속하는 퀵소트를 소개하고자 합니다. 퀵소트 알고리즘은 영역을 계속 분할하여 작은 값은 왼쪽으로 보내고, 큰 값은 오른쪽으로 모는 방식입니다. 그리고
더 이상 분할할 여지가 없다면 정렬은 완성된 것입니다. 그러나 퀵소트가 적합하지 않은 경우도 있습니다. 대표적으로 이미 정렬된 상태의 데이터를 정렬하는 것은 정렬되지 않은 상태의 경우와 비슷한 시간이 걸립니다.
구체적인 정렬방법 개요
정렬할 데이터가 배열에 있다고 했을때
- 정렬할 배열의 상한과 하한값을 구한다.
- 하한값이 상한값보다 작으면 배열을 나눈다.
- 두 배열간 비교하여 교환하고 두 배열의 작업대상도 이동한다.
- 나누어진 각각의 배열에 대해 위의 단계를 반복한다.
이러한 절차를 다음과 같은 하나의 예를 통해 그림으로 표현하면 다음과 같습니다. 이번 예는 총 23단계에 걸쳐 소트가 진행되지만 편의상 원리만 설명하고자 7단계만 설명합니다. 참고로 이번 예와 퀵소트 코드는 제가 만든 것이 아니라 제가 가진 책을 참조했습니다. 즉 다른 말로 하면 베꼈습니다. 책은 Ken Getz와 Mike Gilbert가 공저한
VBA Developer's Handbook 입니다.
원래의 데이터는 79,30,24,48,26,34,05,48,21,86(10개)입니다. 이걸 퀵소트로 정렬하여 보는 겁니다. 위의 그림에서 각 단계를 숫자로 표시하였으며 각 단계를 설명하겠습니다.
1단계:
배열의 하한위치(i)의 값이 상한위치(j)의 값보다 작으면 중간위치(값은 26)를 구합니다. 그리고 하한위치값(79)과 중간위치값(26)보다 작으면 하한위치(i)를 오른쪽으로 증가합니다. 마찬가지로 상한위치값(86)이 중간위치값(26)보다 크면 상한위치(j)를 왼쪽으로 옮긴다. 여기에선 86이 26보다 크므로 한 포인트 옮겨 21을 가리키도록 하였습니다.
i=0
j=9->8로 이동함.
2단계:
하한위치가 상한위치보다 작으면(i<j)이면 서로의 값을 교환합니다.
3단계:
교환후 하한값은 1증가하고(i=i+1) 상한값은 1 감소시킵니다(j=j-1)
i=0->1
j=8->7
4단계:
하한위치값(30)이 중간위치값(26)보다 작지 않으므로 그대로 하한위치는 그대로 두고, 상한위치값(48)이 중간위치값(26)보다 크므로 상한위치를 왼쪽으로 옮겨(j=j-1) 상한위치값이 05가 됩니다. 하한위치가 1이고 상한위치가 6입니다. 하한위치가 상한위치보다 적으므로 서로의 위치값을 교환합니다.
5단계:
3단계와 같이 하한값과 상한값의 위치를 증가/감소시킵니다.
6단계와 7단계 역시 위의 단계를 반복합니다. 이 예에서 정렬이 완료되려면 총23단계를 거칩니다. 사실 이러한 알고리즘을 훤히 알면 좋지만 저 역시 그런 분야를 보면 하품이 나는 처지라 퀵소트가 어떻게 이루어 지는가만 알아 보았습니다.
다음은 퀵소트소스와 사용예입니다.
| Quick Sort소스 |
Attribute VB_Name = "QuickSort"
Option Explicit
' From "VBA Developer's Handbook"
' by Ken Getz and Mike Gilbert
' Copyright 1997; Sybex, Inc. All rights reserved.
' Quicksort for simple data types.
' Indicate that a parameter is missing.
Const dhcMissing = -2
Sub dhQuickSort(varArray As Variant, _
Optional intLeft As Integer = dhcMissing, _
Optional intRight As Integer = dhcMissing)
' From "VBA Developer's Handbook"
' by Ken Getz and Mike Gilbert
' Copyright 1997; Sybex, Inc. All rights reserved.
' Entry point for sorting the array.
' This technique uses the recursive Quicksort
' algorithm to perform its sort.
' In:
' varArray:
'
A variant pointing to an array to be sorted.
'
This had better actually be an array, or the
'
code will fail, miserably. You could add
'
a test for this:
'
If Not IsArray(varArray) Then Exit Sub
'
but hey, that would slow this down, and it's
'
only YOU calling this procedure.
'
Make sure it's an array. It's your problem.
' intLeft:
' intRight:
'
Lower and upper bounds of the array to be sorted.
'
If you don't supply these values (and normally, you won't)
'
the code uses the LBound and UBound functions
'
to get the information. In recursive calls
'
to the sort, the caller will pass this information in.
'
To allow for passing integers around (instead of
'
larger, slower variants), the code uses -2 to indicate
'
that you've not passed a value. This means that you won't
'
be able to use this mechanism to sort arrays with negative
'
indexes, unless you modify this code.
' Out:
'
The data in varArray will be sorted.
Dim i As Integer
Dim j As Integer
Dim varTestVal As Variant
Dim intMid As Integer
If intLeft = dhcMissing Then intLeft = LBound(varArray)
If intRight = dhcMissing Then intRight = UBound(varArray)
If intLeft < intRight Then
intMid = (intLeft + intRight) \ 2
varTestVal = varArray(intMid)
i = intLeft
j = intRight
Do
Do While varArray(i) < varTestVal
i = i + 1
Loop
Do While varArray(j) > varTestVal
j = j - 1
Loop
If i <= j Then
SwapElements varArray, i, j
i = i + 1
j = j - 1
End If
Loop Until i > j
' To optimize the sort, always sort the
' smallest segment first.
If j <= intMid Then
Call dhQuickSort(varArray, intLeft, j)
Call dhQuickSort(varArray, i, intRight)
Else
Call dhQuickSort(varArray, i, intRight)
Call dhQuickSort(varArray, intLeft, j)
End If
End If
End Sub
Private Sub SwapElements(varItems As Variant, intItem1 As Integer, intItem2 As Integer)
Dim varTemp As Variant
varTemp = varItems(intItem2)
varItems(intItem2) = varItems(intItem1)
varItems(intItem1) = varTemp
End Sub
|
Option Explicit
Sub Demo_QuickSort()
Dim varItem
Dim i As Byte
varItem = Array(79, 30, 24, 48, 26, 34, 5, 48, 21, 86)
Call dhQuickSort(varItem)
For i = LBound(varItem) To UBound(varItem)
Debug.Print varItem(i)
Next
End Sub
|
다음 시간에는 소트와 관련한 엑셀과 VBA의 이모저모에 대해 알아볼까 합니다.
|
