Sort 속도 비교 (Quick vs. Bubble)

취미 또는 특기가 프로그래밍이라고 말하던 시절이 있었다. 근데 이 또한 아는 만큼 보이는 법이라 '알고리즘' 따위로 검색하면 골이 어지러울 정도 뻐근한 문제들이 산 처럼 있더라. 데이타 정렬만 해도 버블 정렬 (Bubble Sort)는 무식의 극치요 그걸 코드랍시고 쓴 이는 수준을 의심당한다는데 내가 근 40년 간 그랬다. 뭐, 버블 정렬 만으로도 답답하지 않을 정도 다룬 데이타 규모가 작았다는 말이겠지.

 

앞으로도 험한 꼴 보지 않고 살 수 있으리라는 보장이 없는지라 정렬 중 빠르다는 퀵 정렬 (Quick Sort)와 비교해보기로 했다. 데이타 수가 1,000개 정도 되면 차이가 보기기 시작하더라. 코드는 인터넷에 널린 것 중 하나를 약간 손 봤는데 길이를 더 줄일 수 있는지 앞으로 두고 볼 생각. (2023-08-26토)

study-01 HDD Qsort.xlsm

0.05MB

Sub QSort(varArr As Variant, iLeft As Long, jRight As Long)      'Quick Sort

    Dim i As Long, j As Long
    Dim kMid As Long
    Dim MyVal As Long
        
    If iLeft = -2 Then iLeft = LBound(varArr)
    If jRight = -2 Then jRight = UBound(varArr)
    i = iLeft
    j = jRight
    kMid = Int((i + j) / 2)
 
    If i < j Then
        MyVal = varArr(kMid)
        Do
            Do While varArr(i) < MyVal
                i = i + 1
            Loop
            
            Do While varArr(j) > MyVal
                j = j - 1
            Loop
            
            If i <= j Then
                Call Swap(varArr, 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 <= kMid Then
            Call QSort(varArr, iLeft, j)
            Call QSort(varArr, i, jRight)
        Else
           Call QSort(varArr, i, jRight)
           Call QSort(varArr, iLeft, j)
        End If
    
    End If

End Sub

Sub Swap(varArr As Variant, iL As Long, jR As Long)
    
    Dim TempVal As Long
    
    TempVal = varArr(iL)
    varArr(iL) = varArr(jR)
    varArr(jR) = TempVal
    
End Sub

Sub Sorts()

    Dim l As Long
    Dim n As Long               'total number of array to be sorted
    Dim MyVal As Long
    Dim arr() As Long             'array
    
    Worksheets("Sort").Activate
    n = Range("C2").Value         'number of data
    ReDim arr(n)
    Range("F:H").Cells.Clear

    For l = 1 To n                              'random numbers generation
        MyVal = Round(Rnd * n * 2, 0)
        arr(l) = MyVal
        Cells(l + 5, "F") = MyVal
    Next l
    
    Range("C5").Value = Timer
    Call QSort(arr, -2, -2)
    Range("C6").Value = Timer

    For l = 1 To n                              'write quick sorted result
        Cells(l + 5, "G") = arr(l)
    Next l

    For l = 1 To n
        arr(l) = Cells(l + 5, "F")
    Next l

    Range("D5").Value = Timer
    Call BSort(arr)
    Range("D6").Value = Timer

    For l = 1 To n                              'write bubble sorted result
        Cells(l + 5, "H") = arr(l)
    Next l

End Sub

Sub BSort(varArr As Variant)                'Bubble Sort

    Dim i As Long, j As Long, k As Long
        
    i = LBound(varArr)
    j = UBound(varArr)
    k = j
        
    For i = 1 To k - 1
        For j = i + 1 To k
            If varArr(i) > varArr(j) Then
                Call Swap(varArr, i, j)
            End If
        Next j
    Next i
    
End Sub