Понимание того, как алгоритм быстрой сортировки повторяется в VBA

Question

Я недавно прочитал этот пост: Функция сортировки массива VBA? , чтобы посмотреть, смогу ли я получить некоторый код для реализации алгоритма быстрой сортировки в Excel VBA.

Я взял следующий код изопубликовать и реализовать его в Excel:

   Public Sub QuickSort(vArray As Variant, inLow As Long, inHi As Long)
  Dim pivot   As Variant
  Dim tmpSwap As Variant
  Dim tmpLow  As Long
  Dim tmpHi   As Long

  tmpLow = inLow
  tmpHi = inHi

  pivot = vArray((inLow + inHi) \ 2)

  While (tmpLow <= tmpHi)
     While (vArray(tmpLow) < pivot And tmpLow < inHi)
        tmpLow = tmpLow + 1
     Wend

     While (pivot < vArray(tmpHi) And tmpHi > inLow)
        tmpHi = tmpHi - 1
     Wend

     If (tmpLow <= tmpHi) Then
        tmpSwap = vArray(tmpLow)
        vArray(tmpLow) = vArray(tmpHi)
        vArray(tmpHi) = tmpSwap
        tmpLow = tmpLow + 1
        tmpHi = tmpHi - 1
     End If
  Wend

  If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi
  If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi
End Sub

Затем я пробежал по нему построчно, используя клавишу F8, и, к моему удивлению, он неоднократно выделял строку End Sub, так как последний оператор If был ложным, затем прыгнулПерейти к последнему оператору If, в котором значения tmpLow и inHi изменились!

Я использую значения для массива на этой веб-странице, чтобы попытаться сопоставить построчное отображение, приведенное в первом разделе, сцентр в середине: https://www.bogotobogo.com/Algorithms/quicksort.php

Моя реализация соответствует веб-странице до точки, где 7 и 5 должны быть поменяны местами.На данный момент переменные имеют следующие значения:

inLow = 0
inHi = 2
tmpLow = 2
tmpHi = 0

Как видите, ни один из операторов If не является истинным, поэтому строка переходит к End Sub.Если я затем нажимаю F8 еще раз, выделение переходит к последнему оператору If, и переменные теперь имеют значения:

inLow = 0
inHi = 4
tmpLow = 3
tmpHi = 2

Это происходит несколько раз в течение полного запуска алгоритма.Я никогда не видел этого раньше и не могу придумать объяснения того, как код может переходить из End Sub и как значения переменных могут изменяться без выполнения какого-либо видимого кода.

Я был бы оченьблагодарен за любую помощь в прояснении этого вопроса.

Спасибо,

Саймон.

Answer 1

Следующие строки кода вызывают Sub QuickSort рекурсивно:

  If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi
  If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi

Это означает, что он вызывает Sub QuickSort из своего собственного кода до его завершения.

Если это произойдет, то будет создан так называемый стек вызовов. Этот стек содержит процедуры, которые вызываются, но еще не завершены. И он содержит значения переменных в этой точке.

Вы можете просмотреть этот стек вызовов, используя кнопку ... в Окно Locals .

Теперь, если текущее выполнение Sub QuickSort завершено, но есть записи этого Sub в стеке вызовов, тогда эти записи должны быть продолжены. Для этого указатель процесса переходит к точке кода, которая рекурсивно вызвала Sub. Это будет либо строка If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi, либо строка If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi. Дополнительно будут восстановлены все значения переменных, которые также были помещены в стек. Затем стопка Sub идет дальше от этой точки. Так продолжается до тех пор, пока в стеке не будет больше Sub QuickSort. Вот как работает рекурсия.