Recent

Author Topic: Can bubble sort be implemented recursively?  (Read 12204 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;
  84.   readln;
  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
Ada has check
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 »
thanks for your code y.ivanov

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;
  92.   readln;
  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;
  88. writeln('Press return to end');
  89.   readln;
  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;

 

TinyPortal © 2005-2018