### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Can bubble sort be implemented recursively?  (Read 12203 times)

#### y.ivanov

• Full Member
• Posts: 185
##### Re: Can bubble sort be implemented recursively?
« Reply #30 on: June 11, 2021, 07:47:23 pm »
Bubblesort is probably one of the worst sorting methods, no matter of the initial conditions.
It's a fact that in almost all cases a bubble sort gives terrible performance but, if the array is already sorted, a bubble sort should be the fastest sort of them all.  That's also true when the array is almost sorted and the unsorted elements are contiguous pairs.

Aside from those rare exceptional cases, bubble sorting is definitely not a desirable choice... <chuckle>

You're probably talking about the improved bubblesort variant which checks whether the last pass was without swaps and if so then finishes.

#### 440bx

• Hero Member
• Posts: 2428
##### Re: Can bubble sort be implemented recursively?
« Reply #31 on: June 11, 2021, 09:05:22 pm »
You're probably talking about the improved bubblesort variant which checks whether the last pass was without swaps and if so then finishes.
Unless I am mistaken, a bubblesort determines when to terminate by the absence of swaps.  In a bubblesort, once a pass causes no swaps, the array is sorted and the bubblesort ends.  IOW, it's not an "improvement", it's how a standard bubblesort determines the elements are sorted.

if the elements are already sorted, the bubblesort determines in O(n) that they are sorted, which under normal circumstances, is the optimum.
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

#### Jurassic Pork

• Hero Member
• Posts: 986
##### Re: Can bubble sort be implemented recursively?
« Reply #32 on: June 12, 2021, 11:07:52 am »
hello,
here is a console app with recursive and iterative bubblesort algorithms. EpikTimer is used to measure performance.
Code: Pascal  [Select][+][-]
1. program bubbleSort;
2. {\$mode objfpc}
3. uses sysutils,epiktimer,etpackage;
4. const N = 1000;  {Limite supérieure de tableau}
5. type TTab = array  of integer;   { TTab : Type Tableau }
6. var TabSrc,TabTest : TTab ;
7.
8. generic procedure swap<T>(var a, b: T);
9. var temp: T;
10. begin
11.   temp := a; a := b; b := temp;
12. end;
13.
14. generic procedure recursiveBubbleSort<T>(var arr:array of T;n:integer);
15. var
16. i:integer;
17. begin
18.     if (n = 1) then exit;
19.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then specialize swap<T>(arr[i], arr[i+1]);
20.     specialize recursiveBubbleSort<T>(arr, n-1);
21. end;
22.
23. procedure IterativeBubbleSort(var list: TTab;n:integer);
24. var
25.   i, j: integer;
26.   t: integer;
27. begin
28.   for i := n downto 2 do
29.     for j := 0 to i - 1 do
30.       if list[j] > list[j + 1] then
31.       begin
32.         t := list[j];
33.         list[j] := list[j + 1];
34.         list[j + 1] := t;
35.       end;
36. end;
37.
38. procedure Fill(var Tab:TTab) ;
39. var i : integer;  { i : Indice de tableau de N colonnes }
40. begin
41.  Randomize;
42.  for i := 1 to N do
43.   tab[i]:=random(N+1);
44. end;
45. procedure Display(Tab:TTab) ;
46. { Affichage des N nombres dans les colonnes }
47. var i : integer;
48. begin
49.  writeln('_____________________________________________________');
50.   for i:= 1 to N do
51.    write(Tab[i] : 3, ' | ');writeln;
52.  writeln('_____________________________________________________');
53. End;
54. var    cStart, cStop: Cardinal;
55.        ET: TEpikTimer;
56.        ResIterative, ResRecursive: Extended;
57. begin
58.   ET := TEpikTimer.Create(nil);
59.   ET.Clear;
60.   setLength(TabSrc,N);
61.   Fill(TabSrc);
62.   TabTest := Copy(TabSrc,0,N);
63.   writeln;
64.   writeln('Unsorted Array');
65.   Display(TabTest);
66.   ET.Start;
67.   specialize recursiveBubbleSort<integer>(TabTest,n);
68.   ET.Stop;
69.   ResRecursive := ET.elapsed;
70.   writeln;
71.   writeln('Sorted Array with Recursive BubbleSort');
72.   Display(TabTest);
73.   TabTest := Copy(TabSrc,0,N);
74.   ET.Start;
75.   iterativeBubbleSort(TabTest,n);
76.   ET.Stop;
77.   ResIterative := ET.elapsed;
78.   writeln;
79.   writeln('Sorted Array with Iterative BubbleSort');
80.   Display(TabTest);
81.   Writeln('Recursive BubbleSort time : ' + FloatToStr(ResRecursive));
82.   Writeln('Iterative BubbleSort time : ' + FloatToStr(ResIterative));
83.   ET.Free;
85. end.

example of result for N=1000 :
Quote
Recursive BubbleSort time : 0,00734958892067424
Iterative BubbleSort time : 0,0137503988494744

you can try to  correct and optimize the algorithms      . It seems that there is a problem with first and last element in the result array of recursive algorithm.

Friendly, J.P
« Last Edit: June 12, 2021, 01:04:20 pm by Jurassic Pork »
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

#### y.ivanov

• Full Member
• Posts: 185
##### Re: Can bubble sort be implemented recursively?
« Reply #33 on: June 12, 2021, 11:20:09 am »
You're probably talking about the improved bubblesort variant which checks whether the last pass was without swaps and if so then finishes.
Unless I am mistaken, a bubblesort determines when to terminate by the absence of swaps.  In a bubblesort, once a pass causes no swaps, the array is sorted and the bubblesort ends.  IOW, it's not an "improvement", it's how a standard bubblesort determines the elements are sorted.
Considering the fact we're talking about something with purely educational purpose, what is actualy "the standard bubblesort"?

The Wirth's one (Algorithms+Data structures=programs) has no check,
the Knuth's one (TAOCP) has a last swapped index<>0 check,
the Sedgewick's one (Algorithms) has a first element changed check.

In Rosetta code examples:
Pascal has no check
Delphi has a low water index for the last swap
Modula-2, -3 has checks
C#, C and C++, D has checks
Forth has versions with and without check
Java, Kotlin has check
Pearl has no check
Rust with check
etc.

if the elements are already sorted, the bubblesort determines in O(n) that they are sorted, which under normal circumstances, is the optimum.
BTW, the probability for the array to be sorted is so small that it merely can't affect its overall quadratic complexity.

#### y.ivanov

• Full Member
• Posts: 185
##### Re: Can bubble sort be implemented recursively?
« Reply #34 on: June 12, 2021, 02:01:29 pm »
hello,
here is a console app with recursive and iterative bubblesort algorithms. EpikTimer is used to measure performance.
*snip*
It seems that there is an error in rosettacode example. The correct one must be:
Code: Pascal  [Select][+][-]
1. procedure IterativeBubbleSort(var list: TTab;n:integer);
2. var
3.   i, j: integer;
4.   t: integer;
5. begin
6.   for i := n-1 downto 1 do
7.     for j := 0 to i - 1 do
8.       if list[j] > list[j + 1] then
9.       begin
10.         t := list[j];
11.         list[j] := list[j + 1];
12.         list[j + 1] := t;
13.       end;
14. end;

example of result for N=1000 :
Quote
Recursive BubbleSort time : 0,00734958892067424
Iterative BubbleSort time : 0,0137503988494744
I haven't used the EpikTimer, but it seems that elapsed time for iterative is added to the previous.

you can try to  correct and optimize the algorithms      . It seems that there is a problem with first and last element in the result array of recursive algorithm.

Friendly, J.P

Here is the flag modification discussed:
Code: Pascal  [Select][+][-]
1. generic procedure recursiveBubbleSort<T>(var arr:array of T;n:integer);
2. var
3. i:integer; chg: boolean = false;
4. begin
5.     if (n = 1) then exit;
6.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then begin
7.       specialize swap<T>(arr[i], arr[i+1]); chg := true;
8.     end;
9.     if chg then specialize recursiveBubbleSort<T>(arr, n-1);
10. end;
11.
12. procedure IterativeBubbleSort(var list: TTab;n:integer);
13. var
14.   i, j: integer;
15.   t: integer; chg: boolean = true;
16. begin
17.   {for} i := n - 1; {downto} while (i >= 1) and chg do
18.   begin chg := false;
19.     for j := 0 to i - 1 do
20.       if list[j] > list[j + 1] then
21.       begin
22.         t := list[j];
23.         list[j] := list[j + 1];
24.         list[j + 1] := t; chg := true;
25.       end;
26.     dec(i);
27.   end;
28. end;

Cheers 🍺

#### Jurassic Pork

• Hero Member
• Posts: 986
##### Re: Can bubble sort be implemented recursively?
« Reply #35 on: June 12, 2021, 02:35:57 pm »

for the epiktimer it lacked an ET.clear. there was also an error in the fill and the display procedure :
Code: Pascal  [Select][+][-]
1. for i:= 1 to N do
=>
Code: Pascal  [Select][+][-]
1. for i:= 0 to N-1 do
New code :
Code: Pascal  [Select][+][-]
1. program bubbleSort;
2. {\$mode objfpc}
3. uses sysutils,epiktimer,etpackage;
4. const N = 1000;  {Limite supérieure de tableau}
5. type TTab = array  of integer;   { TTab : Type Tableau }
6. var TabSrc,TabTest : TTab ;
7.
8. generic procedure swap<T>(var a, b: T);
9. var temp: T;
10. begin
11.   temp := a; a := b; b := temp;
12. end;
13.
14. generic procedure recursiveBubbleSort<T>(var arr:array of T;n:integer);
15. var
16. i:integer; chg: boolean = false;
17. begin
18.     if (n = 1) then exit;
19.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then begin
20.       specialize swap<T>(arr[i], arr[i+1]); chg := true;
21.     end;
22.     if chg then specialize recursiveBubbleSort<T>(arr, n-1);
23. end;
24.
25. procedure IterativeBubbleSort(var list: TTab;n:integer);
26. var
27.   i, j: integer;
28.   t: integer; chg: boolean = true;
29. begin
30.   {for} i := n - 1; {downto} while (i >= 1) and chg do
31.   begin chg := false;
32.     for j := 0 to i - 1 do
33.       if list[j] > list[j + 1] then
34.       begin
35.         t := list[j];
36.         list[j] := list[j + 1];
37.         list[j + 1] := t; chg := true;
38.       end;
39.     dec(i);
40.   end;
41. end;
42.
43.
44. procedure Fill(var Tab:TTab) ;
45. var i : integer;  { i : Indice de tableau de N colonnes }
46. begin
47.  Randomize;
48.  for i := 0 to N-1 do
49.   tab[i]:=random(N+1);
50. end;
51.
52. procedure Display(Tab:TTab) ;
53. { Affichage des N nombres dans les colonnes }
54. var i : integer;
55. begin
56.  writeln('_____________________________________________________');
57.   for i:= 0 to N-1 do
58.    write(Tab[i] : 3, ' | ');writeln;
59.  writeln('_____________________________________________________');
60. End;
61. var    cStart, cStop: Cardinal;
62.        ET: TEpikTimer;
63.        ResIterative, ResRecursive: Extended;
64. begin
65.   ET := TEpikTimer.Create(nil);
66.   ET.Clear;
67.   setLength(TabSrc,N);
68.   Fill(TabSrc);
69.   TabTest := Copy(TabSrc,0,N);
70.   writeln;
71.   writeln('Unsorted Array');
72.   Display(TabTest);
73.   ET.Start;
74.   specialize recursiveBubbleSort<integer>(TabTest,n);
75.   ET.Stop;
76.   ResRecursive := ET.elapsed;
77.   writeln;
78.   writeln('Sorted Array with Recursive BubbleSort');
79.   Display(TabTest);
80.   TabTest := Copy(TabSrc,0,N);
81.   ET.Clear;
82.   ET.Start;
83.   iterativeBubbleSort(TabTest,n);
84.   ET.Stop;
85.   ResIterative := ET.elapsed;
86.   writeln;
87.   writeln('Sorted Array with Iterative BubbleSort');
88.   Display(TabTest);
89.   Writeln('Recursive BubbleSort time : ' + FloatToStr(ResRecursive));
90.   Writeln('Iterative BubbleSort time : ' + FloatToStr(ResIterative));
91.   ET.Free;
93. end.

Result for N= 100 :
Quote
Recursive BubbleSort time : 0,00012263134358643
Iterative BubbleSort time : 0,0000840197076941564

Friendly, J.P
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

#### BobDog

• Jr. Member
• Posts: 83
##### Re: Can bubble sort be implemented recursively?
« Reply #36 on: June 12, 2021, 06:14:49 pm »

Very little difference here:
Code: Pascal  [Select][+][-]
1.
2.
3. program comparesorts;
4. {\$mode delphi}
5.  uses
6. SysUtils,DateUtils;
7.
8. procedure bubbleSortRE<T>(var arr:array of T;n:int32);
9. var
10. i:int32;
11. temp:T;
12. begin
13.     if (n = 1) then exit;
14.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then
15.     begin
16.     temp:=arr[i];
17.     arr[i]:=arr[i+1];
18.     arr[i+1]:=temp;
19.     end;
20.     bubbleSortRe<T>(arr, n-1);
21. end;
22.
23. procedure bubbleSortIt<T>(var arr:array of T;n:int32);
24. var
25. i:int32;
26. temp:T;
27. begin
28. while (n>1) do
29.   begin
30.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then
31.     begin
32.     temp:=arr[i];
33.     arr[i]:=arr[i+1];
34.     arr[i+1]:=temp;
35.     end;
36.     n:=n-1;
37.    end;
38. end;
39.
40.
41. function range(f:int32;l:int32):int32;
42.   begin
43.   range:= trunc(random*(l+1-f) ) +f;
44.   end;
45.
46.
47.
48.   const
49.   limit=30000;
50.
51.   var n:int32;
52.   var I :array[0 .. limit] of int32;
53.   var I2:array[0 .. limit] of int32;
54.   var
55.   D1,D2,D3,D4:tdatetime;
56.
57.
58.   begin
59.
60.   randomize;
61.   for n:=0 to limit do
62.   begin
63.   I[n]:=range(0,100000);
64.   I2[n]:=I[n];
65.   end;
66.
67.  writeln('please wait . . .  ',limit+1,' array elements to sort twice ');
68.
69.   D1:=now;
70.   bubblesortre<int32>(I,limit-1);
71.   D2:=now;
72.
73.   D3:=now;
74.   bubblesortit<int32>(I2,limit-1);
75.   D4:=now;
76.
77.
78. for n:=0 to 50 do write(I[n],' ');
79. write(' . . . ');
80. writeln;
81. writeln('Time for recursive ', MilliSecondsBetween(D1, D2), ' milliseconds');
82. writeln;
83. for n:=0 to 50 do write(I2[n],' ');
84. write(' . . . ');
85. writeln;
86. writeln('Time for iterative ', MilliSecondsBetween(D3, D4), ' milliseconds');
87. writeln;
90.   end.
91.
92.
93.
94.

#### PascalDragon

• Hero Member
• Posts: 3170
• Compiler Developer
##### Re: Can bubble sort be implemented recursively?
« Reply #37 on: June 13, 2021, 12:37:28 pm »
It shouldn't be overused, i.e. shouldn't be used, where it's not needed. Because it's costly. It uses stack frame (explicitly or implicitly - even if registers are used to pass parameters, they still need to be stored in stack to preserve their values) to store current state in order to be able to restore it to move up to previous tree level.
Agreed. But it is the recursion implementation what costs, all of the recursion-based languages have tail call optimization, many of the imperative languages also have it. (not sure about fpc)

FPC supports tail recursion optimizations, tough with the restriction that the assignment to the result variable must be a self-recursive call without any further operations:

Code: Pascal  [Select][+][-]
1. program ttailop;
2.
3. {\$OPTIMIZATION TAILREC}
4.
5. function Factorial(aValue: LongInt): LongInt;
6.
7.   function IntFactorial(aValue: LongInt; aResult: LongInt): LongInt;
8.   begin
9.     if aValue = 0 then
10.       IntFactorial := aResult
11.     else
12.       IntFactorial := IntFactorial(aValue - 1, aResult * aValue);
13.   end;
14.
15. begin
16.   Factorial := IntFactorial(aValue, 1);
17. end;
18.
19. begin
20.   Writeln(Factorial(3));
21. end.

The relevant assembly code (note the jump before the .Lj10 label):

Code: ASM  [Select][+][-]
1. .section .text.n_p\$ttailop\$_\$factorial\$longint\$\$longint_\$\$_intfactorial\$longint\$longint\$\$longint,"x"
2.         .balign 16,0x90
3. .globl  P\$TTAILOP\$_\$FACTORIAL\$LONGINT\$\$LONGINT_\$\$_INTFACTORIAL\$LONGINT\$LONGINT\$\$LONGINT
4. P\$TTAILOP\$_\$FACTORIAL\$LONGINT\$\$LONGINT_\$\$_INTFACTORIAL\$LONGINT\$LONGINT\$\$LONGINT:
5. .Lc6:
6. .seh_proc P\$TTAILOP\$_\$FACTORIAL\$LONGINT\$\$LONGINT_\$\$_INTFACTORIAL\$LONGINT\$LONGINT\$\$LONGINT
7. # [8] begin
8.         pushq   %rbp
9. .seh_pushreg %rbp
10. .Lc8:
11. .Lc9:
12.         movq    %rsp,%rbp
13. .Lc10:
14.         leaq    -64(%rsp),%rsp
15. .seh_stackalloc 64
16. .seh_endprologue
17. # Var aValue located at rbp-8, size=OS_S32
18. # Var aResult located at rbp-16, size=OS_S32
19. # Var \$parentfp located at rbp-24, size=OS_64
20. # Var \$result located at rbp-28, size=OS_S32
21.         movq    %rcx,-24(%rbp)
22.         movl    %edx,-8(%rbp)
23.         movl    %r8d,-16(%rbp)
24. .Lj7:
25. # [9] if aValue = 0 then
26.         cmpl    \$0,-8(%rbp)
27.         je      .Lj8
28.         jmp     .Lj9
29. .Lj8:
30. # [10] IntFactorial := aResult
31.         movl    -16(%rbp),%eax
32.         movl    %eax,-28(%rbp)
33.         jmp     .Lj10
34. .Lj9:
35. # [12] IntFactorial := IntFactorial(aValue - 1, aResult * aValue);
36.         movl    -16(%rbp),%edx
37.         movl    -8(%rbp),%eax
38.         imull   %edx,%eax
39.         movl    -8(%rbp),%edx
40.         leal    -1(%edx),%edx
41.         movq    -24(%rbp),%rcx
42.         movl    %eax,-16(%rbp)
43.         movl    %edx,-8(%rbp)
44.         movq    %rcx,-24(%rbp)
45.         jmp     .Lj7
46. .Lj10:
47. # [13] end;
48.         movl    -28(%rbp),%eax
49.         nop
50.         leaq    (%rbp),%rsp
51.         popq    %rbp
52.         ret
53. .seh_endproc
54. .Lc7:
55.

The following code will not be optimized in that regard however:

Code: Pascal  [Select][+][-]
1. function Factorial(aValue: LongInt): LongInt;
2. begin
3.   if aValue = 0 then
4.     Factorial := 1
5.   else
6.     Factorial := Factorial(aValue - 1) * aValue;
7. end;

Also FPC 3.3.1 supports open array parameters for tail recursion optimizations:

Code: Pascal  [Select][+][-]
1. function SumL(const Values: array of Integer): Integer;
2.
3.   function SumInt(const Values: array of Integer; Res: Integer): Integer;
4.   begin
5.     if Length(Values) = 0 then
6.       SumInt := Res
7.     else
8.       SumInt := SumInt(Values[0..High(Values) - 1], Res + Values[High(Values)]);
9.   end;
10.
11. begin
12.   SumL := SumInt(Values, 0);
13. end;