Recursive Vrs NonRecursive test with Quicksort

[bplus]

Seeing Sanmayce Quicksort test with my recursive Quicksort I had to try my own test without using the array in the parameters/arguments call, plus in the Discussion Board Recursion topic brought up some ideas from Luke on recursion that I've been curious experimenting with for some time.

So here's my quick test:

Code: QB64: [Select]

1. _Title "Recursive Vrs NonRecursive test with Quicksort" 'b+ 2021-11-01
2. _Define A-Z As _UNSIGNED _INTEGER64
3. ReDim Shared As _Unsigned _Integer64 ArrayHigh
4. ArrayHigh = 100000000
5. ReDim Shared As _Unsigned _Integer64 n(1 To ArrayHigh), m(1 To ArrayHigh)
6.  
7. For i = 1 To ArrayHigh
8.     n(i) = i
9. Next
10. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
11.     Swap n(i), n(Int(Rnd * i) + 1)
12.     m(i) = n(i) ' copy m off n
13. Next
14. Print "Test arrays ready. Testing Recursive QuickSort first."
15. m(1) = n(1)
16. T# = Timer(.001)
17. QuickSort 1, ArrayHigh
18. QuickSortT# = Timer(.001) - T#
19. For i = 1 To ArrayHigh
20.     If n(i) <> i Then Beep: Print "Error in QuickSort array n."
21. Next
22. Print "QuickSort checked, QuickSort time was"; QuickSortT#
23.  
24. T# = Timer(.001)
25. Quicksort_QB64
26. QuicksortQB64T# = Timer(.001) - T#
27. For i = 1 To ArrayHigh
28.     If m(i) <> i Then Beep: Print "Error in Quicksort__QB64 array m."
29. Next
30. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
31.  
32. ' recursive
33. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
34.     Lo = start: Hi = finish
35.     Middle = n((Lo + Hi) \ 2)
36.     Do
37.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
38.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
39.         If Lo <= Hi Then
40.             Swap n(Lo), n(Hi)
41.             Lo = Lo + 1: Hi = Hi - 1
42.         End If
43.     Loop Until Lo > Hi
44.     If Hi > start Then QuickSort start, Hi
45.     If Lo < finish Then QuickSort Lo, finish
46. End Sub
47.  
48. ' non recursive
49. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
50. Sub Quicksort_QB64
51.     Left = LBound(m)
52.     Right = UBound(m)
53.     LeftMargin = Left
54.     ReDim Stack&&(Left To Right)
55.     StackPtr = 0
56.     StackPtr = StackPtr + 1
57.     Stack&&(StackPtr + LeftMargin) = Left
58.     StackPtr = StackPtr + 1
59.     Stack&&(StackPtr + LeftMargin) = Right
60.     Do 'Until StackPtr = 0
61.         Right = Stack&&(StackPtr + LeftMargin)
62.         StackPtr = StackPtr - 1
63.         Left = Stack&&(StackPtr + LeftMargin)
64.         StackPtr = StackPtr - 1
65.         Do 'Until Left >= Right
66.             Pivot~&& = m((Left + Right) \ 2)
67.             Indx = Left
68.             Jndx = Right
69.             Do
70.                 Do While (m(Indx) < Pivot~&&)
71.                     Indx = Indx + 1
72.                 Loop
73.                 Do While (m(Jndx) > Pivot~&&)
74.                     Jndx = Jndx - 1
75.                 Loop
76.                 If Indx <= Jndx Then
77.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
78.                     Indx = Indx + 1
79.                     Jndx = Jndx - 1
80.                 End If
81.             Loop While Indx <= Jndx
82.             If Indx < Right Then
83.                 StackPtr = StackPtr + 1
84.                 Stack&&(StackPtr + LeftMargin) = Indx
85.                 StackPtr = StackPtr + 1
86.                 Stack&&(StackPtr + LeftMargin) = Right
87.             End If
88.             Right = Jndx
89.         Loop Until Left >= Right
90.     Loop Until StackPtr = 0
91. End Sub
92.  
93.  

Nice non recursion code, doing it with your own stack is interesting. I don't suppose there's a way to do a recursive quicksort without need of any parameters to call? Hmm...


EDIT: Dang it! I never use Call this is what I get for copying what I thought was my code from someone else post. :(
EDIT: Fix a labeling if error found in 2nd test.

[jack]

bplus, I don't quite agree with your definition of non-recursive
looks like a dirty hack and not a real non-recursive quick-sort, don't know that it's even possible

[bplus]

bplus, I don't quite agree with your definition of non-recursive
looks like a dirty hack and not a real non-recursive quick-sort, don't know that it's even possible

Hi Jack,

My definition of non recursive subroutine is one that doesn't call itself to do the job. That draws the line pretty clearly to me.

What may be in question is if the non recursive routine (Sanmayce's post at Rosetta Code) is truly in spirit of Quicksort algorithm and I think it works exactly the same using pivots and working left and right sections of pivot with 2 indexes.

What doesn't look real to you? The stack and it's pointer?

[jack]

bplus, you are basically simulating recursion not replacing it

[Dimster]

Hi as well Jack - It does seem natural that recursive means multiple iteration to the same code. So I was looking at it as perhaps a loop in the main program invoking a sub/function multiple times. But as I'm beginning to learn, recursive means a routine CALLING itself. Steve just provided a recursive routine using IF statements which I'm still trying to make fit into the new definition of recursiveness that I'm formulating. I would be interested in what "Recursive" ( in terms of our use of QB64 coding) means to you.

[bplus]

Looking at Wiki article on Quicksort, it is described as recursive. But does that mean it's not a Quicksort routine if not done recursively? I think not.

What I'd really like to see is if anyone can do Quicksort recursively without parameters in the call to itself!

Jack described the non recursive routine as ugly, I agree, recursive routines are much more elegant (unless you try to hack a no parameters routine for Quicksort LOL).

[TempodiBasic]

Hi dear friends

about Quicksort
starting with a unordered finished set of homogeneus values
to get the goal to order this set
 1. pickup a cutoff value
 2. from its left move to right (over) the greater values than it
 3. from its right move to left (under) the smaller values than it
 4. do again this work for subset left and right of this pivot (here it can entry the recursive method in alternative to iterative method)

-------------
about Iterative quicksort routine posted on Rosetta Code  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
it uses confounding name of variables but surely it is not an emulation of stack, moreover to be iterative you must keep trace of your pivot values and Left values and Right values to be sure to run code UNTIL all subsets >1 are evaluated and ordered.

So surely in the iterative way you must write the code to keep value of pivot and left margin and right margin around the loop of a single run of Quicksort (the point n°4 of the overtype scheme)
the best choice seems to be the tail that is a LIFO structure.

here some web informations
https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
https://www.techiedelight.com/iterative-implementation-of-quicksort/
https://www.geeksforgeeks.org/iterative-quick-sort/?ref=lbp

       Happy study

[bplus]

I don't know if you guys are understanding what I am doing here. It is just a speed test between a Quicksort recursive subroutine versus a very nice non recursive Quicksort routine that does the very same thing only slightly faster and it does it by emulating how a recursive subroutine works with internal stack by providing a sort (no pun intended) of pseudo stack in the non recursive routine.

[bplus]

I did it, created recursive Quicksort routine without parameters! I used a Shared Stack array and Stack pointer. It is the third test added to the other 2:

Code: QB64: [Select]

1. _Title "Recursive Vrs NonRecursive #2 test with Quicksort" 'b+ 2021-11-01
2. '2021-11-01 #2 test try a recursive sub wo parameters
3.  
4. _Define A-Z As _UNSIGNED _INTEGER64
5. ReDim Shared As _Unsigned _Integer64 ArrayHigh, StackPt
6. ArrayHigh = 10000000
7. ReDim Shared n(1 To ArrayHigh), m(1 To ArrayHigh), o(1 To ArrayHigh)
8. ReDim Shared Stack(0 To ArrayHigh \ 8)
9.  
10. For i = 1 To ArrayHigh
11.     n(i) = i
12. Next
13. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
14.     Swap n(i), n(Int(Rnd * i) + 1)
15.     m(i) = n(i) ' copy m off n
16.     o(i) = n(i)
17. Next
18. m(1) = n(1)
19. o(1) = n(1)
20. Print "Test arrays ready. Testing Recursive QuickSort first."
21.  
22. T# = Timer(.001)
23. QuickSort 1, ArrayHigh
24. QuickSortT# = Timer(.001) - T#
25. For i = 1 To ArrayHigh
26.     If n(i) <> i Then Beep: Print "Error in QuickSort array n."
27. Next
28. Print "QuickSort checked, QuickSort time was"; QuickSortT#
29.  
30. T# = Timer(.001)
31. Quicksort_QB64
32. QuicksortQB64T# = Timer(.001) - T#
33. For i = 1 To ArrayHigh
34.     If m(i) <> i Then Beep: Print "Error in Quicksort__QB64 array m."
35. Next
36. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
37.  
38. T# = Timer(.001)
39. StackPt = StackPt + 1
40. Stack(StackPt) = 1
41. StackPt = StackPt + 1
42. Stack(StackPt) = ArrayHigh
43. QSort
44. QSortT# = Timer(.001) - T#
45. For i = 1 To ArrayHigh
46.     If o(i) <> i Then Beep: Print "Error in QSort array o."
47. Next
48. Print "QSort checked, QSort time was"; QSortT#
49.  
50. ' recursive
51. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
52.     Lo = start: Hi = finish
53.     Middle = n((Lo + Hi) \ 2)
54.     Do
55.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
56.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
57.         If Lo <= Hi Then
58.             Swap n(Lo), n(Hi)
59.             Lo = Lo + 1: Hi = Hi - 1
60.         End If
61.     Loop Until Lo > Hi
62.     If Hi > start Then QuickSort start, Hi
63.     If Lo < finish Then QuickSort Lo, finish
64. End Sub
65.  
66. ' non recursive
67. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
68. Sub Quicksort_QB64
69.     Left = LBound(m)
70.     Right = UBound(m)
71.     LeftMargin = Left
72.     ReDim Stack&&(Left To Right)
73.     StackPtr = 0
74.     StackPtr = StackPtr + 1
75.     Stack&&(StackPtr + LeftMargin) = Left
76.     StackPtr = StackPtr + 1
77.     Stack&&(StackPtr + LeftMargin) = Right
78.     Do 'Until StackPtr = 0
79.         Right = Stack&&(StackPtr + LeftMargin)
80.         StackPtr = StackPtr - 1
81.         Left = Stack&&(StackPtr + LeftMargin)
82.         StackPtr = StackPtr - 1
83.         Do 'Until Left >= Right
84.             Pivot~&& = m((Left + Right) \ 2)
85.             Indx = Left
86.             Jndx = Right
87.             Do
88.                 Do While (m(Indx) < Pivot~&&)
89.                     Indx = Indx + 1
90.                 Loop
91.                 Do While (m(Jndx) > Pivot~&&)
92.                     Jndx = Jndx - 1
93.                 Loop
94.                 If Indx <= Jndx Then
95.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
96.                     Indx = Indx + 1
97.                     Jndx = Jndx - 1
98.                 End If
99.             Loop While Indx <= Jndx
100.             If Indx < Right Then
101.                 StackPtr = StackPtr + 1
102.                 Stack&&(StackPtr + LeftMargin) = Indx
103.                 StackPtr = StackPtr + 1
104.                 Stack&&(StackPtr + LeftMargin) = Right
105.             End If
106.             Right = Jndx
107.         Loop Until Left >= Right
108.     Loop Until StackPtr = 0
109. End Sub
110.  
111. ' recursive No Parameters!!!
112. Sub QSort
113.     If StackPt > 0 Then 'else done!
114.         finish = Stack(StackPt) 'pull off last 2 arguments
115.         StackPt = StackPt - 1
116.         start = Stack(StackPt)
117.         StackPt = StackPt - 1
118.  
119.         Lo = start: Hi = finish
120.         Middle = o((Lo + Hi) \ 2)
121.         Do
122.             Do While o(Lo) < Middle: Lo = Lo + 1: Loop
123.             Do While o(Hi) > Middle: Hi = Hi - 1: Loop
124.             If Lo <= Hi Then
125.                 Swap o(Lo), o(Hi)
126.                 Lo = Lo + 1: Hi = Hi - 1
127.             End If
128.         Loop Until Lo > Hi
129.  
130.         If Hi > start Then
131.             StackPt = StackPt + 1
132.             Stack(StackPt) = start
133.             StackPt = StackPt + 1
134.             Stack(StackPt) = Hi
135.             QSort
136.         End If
137.         If Lo < finish Then
138.             StackPt = StackPt + 1
139.             Stack(StackPt) = Lo
140.             StackPt = StackPt + 1
141.             Stack(StackPt) = finish
142.             QSort
143.         End If
144.     End If
145. End Sub
146.  
147.  
148.  

Surprise! It turns out that it takes longer to play with a pseudo stack loading and resetting pointer than it does to call the Quicksort routine with parameters, a fairly significant amount of time longer.

[Sanmayce]

Thank you @bplus for your tests.
In the morning did write the 'Magnetica' partitioning, which helps greatly in "few distinct keys" scenario, usually 15x to 3x speed boost it gives. However, it hurts speed badly (2x) in "many distinct keys", the problem lies in STILL not well written right part traversal (Jndx), doing unnecessary swaps has to be fixed...
Your test (modified) is given below with ability (just change line 8) to run in "few distinct keys", otherwise it is the most common "many distinct keys":

 

"few distinct keys" scenario:

 

Code: QB64: [Select]

1. _Title "Recursive Vrs NonRecursive test with Quicksort" 'b+ 2021-11-01, Sanmayce added some stuff 2021-Nov-04
2. _Define A-Z As _UNSIGNED _INTEGER64
3. ReDim Shared As _Unsigned _Integer64 ArrayHigh
4. ArrayHigh = 10000000
5. ReDim Shared As _Unsigned _Integer64 n(1 To ArrayHigh), m(1 To ArrayHigh), z(1 To ArrayHigh)
6.  
7. For i = 1 To ArrayHigh
8.     n(i) = i '13 'i
9. Next
10. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
11.     Swap n(i), n(Int(Rnd * i) + 1)
12.     m(i) = n(i) ' copy m off n
13.     z(i) = n(i) ' copy m off n
14. Next
15. Print "Test arrays ready. Testing Recursive QuickSort first."
16. n(1) = ArrayHigh
17. m(1) = n(1)
18. z(1) = n(1)
19.  
20. T# = Timer(.001)
21. QuickSort 1, ArrayHigh
22. QuickSortT# = Timer(.001) - T#
23. For i = 1 To ArrayHigh - 1
24.     If n(i) > n(i + 1) Then Print "NOT OK!": End
25. Next
26. Print "QuickSort checked, QuickSort time was"; QuickSortT#
27.  
28.  
29. T# = Timer(.001)
30. Quicksort_QB64
31. QuicksortQB64T# = Timer(.001) - T#
32. For i = 1 To ArrayHigh - 1
33.     If m(i) > m(i + 1) Then Print "NOT OK!": End
34. Next
35. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
36.  
37.  
38. T# = Timer(.001)
39. Quicksort_QB64_v2
40. QuicksortQB64T# = Timer(.001) - T#
41. For i = 1 To ArrayHigh - 1
42.     If z(i) > z(i + 1) Then Print "NOT OK!": End
43. Next
44. Print "Quicksort_QB64_v2 checked, Quicksort_QB64_v2 time was"; QuicksortQB64T#
45.  
46.  
47.  
48. ' recursive
49. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
50.     Lo = start: Hi = finish
51.     Middle = n((Lo + Hi) \ 2)
52.     Do
53.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
54.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
55.         If Lo <= Hi Then
56.             Swap n(Lo), n(Hi)
57.             Lo = Lo + 1: Hi = Hi - 1
58.         End If
59.     Loop Until Lo > Hi
60.     If Hi > start Then QuickSort start, Hi
61.     If Lo < finish Then QuickSort Lo, finish
62. End Sub
63.  
64. ' non recursive
65. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
66. Sub Quicksort_QB64
67.     Left = LBound(m)
68.     Right = UBound(m)
69.     LeftMargin = Left
70.     ReDim Stack&&(Left To Right)
71.     StackPtr = 0
72.     StackPtr = StackPtr + 1
73.     Stack&&(StackPtr + LeftMargin) = Left
74.     StackPtr = StackPtr + 1
75.     Stack&&(StackPtr + LeftMargin) = Right
76.     Do 'Until StackPtr = 0
77.         Right = Stack&&(StackPtr + LeftMargin)
78.         StackPtr = StackPtr - 1
79.         Left = Stack&&(StackPtr + LeftMargin)
80.         StackPtr = StackPtr - 1
81.         Do 'Until Left >= Right
82.             Pivot~&& = m((Left + Right) \ 2)
83.             Indx = Left
84.             Jndx = Right
85.             Do
86.                 Do While (m(Indx) < Pivot~&&)
87.                     Indx = Indx + 1
88.                 Loop
89.                 Do While (m(Jndx) > Pivot~&&)
90.                     Jndx = Jndx - 1
91.                 Loop
92.                 If Indx <= Jndx Then
93.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
94.                     Indx = Indx + 1
95.                     Jndx = Jndx - 1
96.                 End If
97.             Loop While Indx <= Jndx
98.             If Indx < Right Then
99.                 StackPtr = StackPtr + 1
100.                 Stack&&(StackPtr + LeftMargin) = Indx
101.                 StackPtr = StackPtr + 1
102.                 Stack&&(StackPtr + LeftMargin) = Right
103.             End If
104.             Right = Jndx
105.         Loop Until Left >= Right
106.     Loop Until StackPtr = 0
107. End Sub
108.  
109.  
110. Sub Quicksort_QB64_v2
111.     Left = LBound(z)
112.     Right = UBound(z)
113.     ReDim Stack&&(Left To Right)
114.     StackPtr = 0
115.     StackPtr = StackPtr + 1
116.     Stack&&(StackPtr + LeftMargin) = Left
117.     StackPtr = StackPtr + 1
118.     Stack&&(StackPtr + LeftMargin) = Right
119.     Do 'Until StackPtr = 0
120.         Right = Stack&&(StackPtr)
121.         Left = Stack&&(StackPtr - 1)
122.         StackPtr = StackPtr - 2
123.         Do 'Until Left >= Right
124.  
125.             ' 'Classica' partitioning [
126.             'Pivot~&& = z((Left + Right) \ 2)
127.             'Indx = Left
128.             'Jndx = Right
129.             'Do
130.             '    Do While (z(Indx) < Pivot~&&)
131.             '        Indx = Indx + 1
132.             '    Loop
133.             '    Do While (z(Jndx) > Pivot~&&)
134.             '        Jndx = Jndx - 1
135.             '    Loop
136.             '    If Indx <= Jndx Then
137.             '        If Indx < Jndx Then Swap z(Indx), z(Jndx)
138.             '        Indx = Indx + 1
139.             '        Jndx = Jndx - 1
140.             '    End If
141.             'Loop While Indx <= Jndx
142.             ' 'Classica' partitioning ]
143.  
144.             ' 'Magnetica' partitioning [
145.             Jndx = Right
146.             PL = Left
147.             PR = Left
148.             Swap z((Left + Right) \ 2), z(PL)
149.             Do While PR < Jndx
150.                 If z(PR) > z(PR + 1) Then
151.                     Swap z(PL), z(PR + 1)
152.                     PL = PL + 1
153.                     PR = PR + 1
154.                 ElseIf z(PR) = z(PR + 1) Then
155.                     PR = PR + 1
156.                 Else '<
157.                     Swap z(PR + 1), z(Jndx)
158.                     Jndx = Jndx - 1
159.                 End If
160.             Loop
161.             Jndx = PL - 1
162.             Indx = PR + 1
163.             ' 'Magnetica' partitioning ]
164.  
165.             If Indx < Right Then
166.                 StackPtr = StackPtr + 2
167.                 Stack&&(StackPtr - 1) = Indx
168.                 Stack&&(StackPtr) = Right
169.             End If
170.             Right = Jndx
171.         Loop Until Left >= Right
172.     Loop Until StackPtr = 0
173. End Sub
174.  

Consider having two records/fields (list of all living 7 billion people names with their birth date), now, the second column/field if it is to be sorted we cannot afford using the "Classica" partitioning because we enter the "few distinct keys" scenario with some 100 unique values. I am against "patches" of some pseudo-smart heuristics trying  to adapt "on the fly" to the type of keys in use, rather, I would prefer having two dedicated subroutines, one dealing with "few" the other with "many".
Of course if we can come up with fixing the "Magnetica" then there will be one subroutine only, nice and dirty-cheap, heh-heh.

Also, very often one needs sorting all the files on some drive by their year, not a good feeling 'Classica' to force you wait  7 seconds as in example above for 10,000,000 files.
In practice, there are more brutal sort cases, such as sorting occurrences of 600 billion English 5-grams (phrases of 5 words), the nasty 600GB x 4bytes =~2TB.

You are right @jack, but there is one aspect you should consider, being dirty from what standpoint!
As far as I know, using runtime stack (in addition to program's needs) is not a good practice, saw few discussions in the past where some Linux kernel gurus explicitly stated recursive code is not welcome at all, the topic was some very refined B-tree implementation, but recursive. Simply, the stack is considered an internal zone, endangered in case of entering deep recursion or for some reason stack being used extensively to the brim, hah-hah, hence the super popular stackoverflow site.

Oof, forgot to share the benchmarks done on some modern machines:
https://www.overclock.net/threads/benchmark-quicksort-says-sorting-2-billion-qwords.1794855/