How can I quicksort an array of objects by a property in VBA?

Question

I'm having trouble getting a quicksort algorithm to work in VBA when trying to sort objects by a property. A bubblesort works fine. I think it has to do with object references, but I can't seem to get it right. Bubblesort used to fail, too, until I added a clone method to my object.

Here is a pastebin of relevant supporting code: http://pastebin.com/egcph0jJ .

This is the relevant function:

Private Sub quick_sort_file_array_by_modified(file_array As Variant, inLowBound As Long, inHighBound As Long)

  'Do a quicksort on date_modified

  Dim pivot   As ParsedFile
  Dim tmpSwap As ParsedFile
  Dim tmpLow  As Long
  Dim tmpHi   As Long

  tmpLow = inLowBound
  tmpHi = inHighBound

  Set pivot = file_array((inLowBound + inHighBound) / 2)

  While (tmpLow <= tmpHi)

    Dim tmp_low_file As ParsedFile
    Set tmp_low_file = file_array(tmpLow)

     While (tmp_low_file.file_mod_date < pivot.file_mod_date And tmpLow < inHighBound)
        tmpLow = tmpLow + 1
     Wend

     Dim tmp_high_file As ParsedFile
     Set tmp_high_file = file_array(tmpHi)

     While (pivot.file_mod_date < tmp_high_file.file_mod_date And tmpHi > inLowBound)
        tmpHi = tmpHi - 1
     Wend

     If (tmpLow <= tmpHi) Then
        Set tmpSwap = file_array(tmpLow)
        Set file_array(tmpLow) = file_array(tmpHi).clone
        Set file_array(tmpHi) = tmpSwap.clone
        tmpLow = tmpLow + 1
        tmpHi = tmpHi - 1
     End If

  Wend

  If (inLowBound < tmpHi) Then quick_sort_file_array_by_modified file_array, inLowBound, tmpHi
  If (tmpLow < inHighBound) Then quick_sort_file_array_by_modified file_array, tmpLow, inHighBound


End Sub

... the result is it doesn't really change the order of the object array at all.

LeY · Accepted Answer · 2014-06-08 08:06:08Z

Your quicksort algorithm is wrong.

While (tmp_low_file.file_mod_date < pivot.file_mod_date And tmpLow < inHighBound)
        tmpLow = tmpLow + 1
Wend

You only update your index counter, but you don't update your comparison values "tmp_low_file.file_mod_date < pivot.file_mod_date" alway stay the same, and you tmpLow will go up until inHighBound.

Run this test code, you will see where is wrong.

Public Sub test()
    changedArr = Array(2, 1, 33, 89, 76, 10, 11)
    quick_sort_file_array_by_modified changedArr, 0, 6
End Sub

Private Sub quick_sort_file_array_by_modified(file_array As Variant, inLowBound As Long, inHighBound As Long)

    'Do a quicksort on date_modified

      Dim pivot   As Integer
      Dim tmpSwap As Integer
      Dim tmpLow  As Long
      Dim tmpHi   As Long
      Debug.Print "inLowBound: "; CStr(inLowBound) & "  inHighBound:" & CStr(inHighBound)
      PrintArr file_array
      tmpLow = inLowBound
      tmpHi = inHighBound

      pivot = file_array((inLowBound + inHighBound) / 2)

      Debug.Print "Pivot Value:" & pivot

      While (tmpLow <= tmpHi)

        Dim tmp_low_file As Integer
        tmp_low_file = file_array(tmpLow)

         While (tmp_low_file < pivot And tmpLow < inHighBound)
            tmpLow = tmpLow + 1
         Wend



         Dim tmp_high_file As Integer
         tmp_high_file = file_array(tmpHi)

         While (pivot < tmp_high_file And tmpHi > inLowBound)
            tmpHi = tmpHi - 1
         Wend

         If (tmpLow <= tmpHi) Then

            Debug.Print "Swaping: " & CStr(tmpLow) & " to "; CStr(tmpHi)

            tmpSwap = file_array(tmpLow)
            file_array(tmpLow) = file_array(tmpHi)
            file_array(tmpHi) = tmpSwap
            tmpLow = tmpLow + 1
            tmpHi = tmpHi - 1
         End If
         PrintArr file_array
      Wend

      Debug.Print "inLowBound: "; CStr(inLowBound) & "  tmpHi:" & CStr(tmpHi)
      Debug.Print "tmpLow: "; CStr(tmpLow) & "  inHighBound:" & CStr(inHighBound)

      If (inLowBound < tmpHi) Then
        Debug.Print "calling case inLowBound < tmpHi"
        Debug.Print "---------------------------------"
        quick_sort_file_array_by_modified file_array, inLowBound, tmpHi
      End If

      If (tmpLow < inHighBound) Then
        Debug.Print "calling case tmpLow < inHighBound"
        Debug.Print "---------------------------------"
        quick_sort_file_array_by_modified file_array, tmpLow, inHighBound
      End If

End Sub


Private Sub PrintArr(arr As Variant)
    Dim a As Variant
    Dim result As String
    For Each a In arr
        result = result & CStr(a) & "  "
    Next
    Debug.Print result
End Sub

Collectives™ on Stack Overflow

How can I quicksort an array of objects by a property in VBA?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related