Lazarus

Programming => General => Topic started by: ankitdixit on June 10, 2021, 10:10:15 am

Title: Can bubble sort be implemented recursively?
Post by: ankitdixit on June 10, 2021, 10:10:15 am
Hello All, I want to know, Can bubble sort be implemented recursively? If yes, Can anyone expalin this with some examples?
Title: Re: Can bubble sort be implemented recursively?
Post by: Kays on June 10, 2021, 10:40:05 am
[…] Can bubble sort be implemented recursively?
Certainly it can be.
If yes, Can anyone expalin this with some examples?
Yes, anyone can do this with “examples” (aka homework solution).
Title: Re: Can bubble sort be implemented recursively?
Post by: Zvoni on June 10, 2021, 11:24:58 am
trying google with "recursive bubble sort" this is the first hit
https://www.geeksforgeeks.org/recursive-bubble-sort/

EDIT:
[SARCASM ON]
Now that's a shame: No Pascal sample-code...... only C++, Java, Python, C# and JS....
[SARCASM OFF]
Title: Re: Can bubble sort be implemented recursively?
Post by: ankitdixit on June 10, 2021, 12:12:03 pm
Hey thanks! I am also found this information on geeksforgeeks and Interviewbit (https://www.interviewbit.com/tutorial/bubble-sort/) with one great example

recursiveBubbleSort(arr[], n){
        // Base case
        if (n == 1)
        return;

        // One pass of bubble sort. After
        // this pass, the largest element
        // is moved (or bubbled) to end.
        for(i=0; i<n-1; i++){
            if(arr > arr[i+1])
            {
             swap(arr, arr[i+1]);
            }
        }

        // recursion for remaining elements in array
        recursiveBubbleSort(arr, n-1);
    }
Title: Re: Can bubble sort be implemented recursively?
Post by: Zvoni on June 10, 2021, 12:14:33 pm
Your point?
Title: Re: Can bubble sort be implemented recursively?
Post by: cdbc on June 10, 2021, 12:22:06 pm
Hi
C# is the easiest to translate to pascal  ;)
Regards Benny
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov on June 10, 2021, 02:30:09 pm
It is more of a stone than a bubble ;), but anyway ...

The C function
Code: C  [Select][+][-]
  1. void bubbleSort(int arr[], int n)
  2. {
  3.     // Base case
  4.     if (n == 1)
  5.         return;
  6.  
  7.     // One pass of bubble sort. After
  8.     // this pass, the largest element
  9.     // is moved (or bubbled) to end.
  10.     for (int i=0; i<n-1; i++)
  11.         if (arr[i] > arr[i+1])
  12.             swap(arr[i], arr[i+1]);
  13.  
  14.     // Largest element is fixed,
  15.     // recur for remaining array
  16.     bubbleSort(arr, n-1);
  17. }

should be translated to something like:
Code: Pascal  [Select][+][-]
  1. procedure BubbleSort(A: array of Integer; N: Integer);
  2. var
  3.   I, tmp: Integer;
  4. begin
  5.   if N = 1 then
  6.     Exit;
  7.   for I := 0 to N-1 do
  8.     if A[I] > A[I+1] then
  9.     begin
  10.       tmp := A[I]; A[I] := A[I+1]; A[I+1] := tmp;
  11.     end;
  12.   BubbleSort(A, N-1);
  13. end;

Quote
Can bubble sort be implemented recursively?

Theory says the iteration is a special case of recursion, so any algorithm can be expressed (in theory) recursively.

Edit: It has wrong N+1 instead of N-1 at the recursive call.
Title: Re: Can bubble sort be implemented recursively?
Post by: Jurassic Pork on June 10, 2021, 02:54:05 pm
hello,
one solution (sorry in french) :
Code: Pascal  [Select][+][-]
  1. program bubbleSort;
  2. const N = 100;  {Limite supérieure de tableau}
  3. type TTab = array [1..N] of integer;   { TTab : Type Tableau }
  4. var Tab : TTab ;
  5. Procedure Tri_bulles (var t : TTab; n : integer);
  6. Var i, aux : integer;
  7.     Function Trier (t : TTAB; n : integer) : Boolean;
  8.     Var ok : boolean; i : integer;
  9.     Begin
  10.          ok := true; i := 1;
  11.          Repeat
  12.                If t[i + 1] < t[i] Then ok := false
  13.                Else i := i + 1;
  14.          Until ((Not ok) or (i >= n));
  15.          Trier := ok;
  16.     End;
  17.     Begin
  18.          If Not Trier (t, n) Then
  19.          Begin
  20.               For i := 1 To n - 1 Do
  21.                 If t[i] > t[i + 1] Then
  22.                    Begin
  23.                         aux := t[i];
  24.                         t[i] := t[i + 1];
  25.                         t[i + 1] := aux;
  26.                    End;
  27.               Tri_bulles (t, n);
  28.          End;
  29.     End;
  30. procedure Remplir(var Tab:TTab) ;
  31. var i : integer;  { i : Indice de tableau de N colonnes }
  32. begin
  33.  Randomize;
  34.  for i := 1 to N do
  35.   tab[i]:=random(N+1);
  36. end;
  37. procedure Affichage(Tab:TTab) ;
  38. { Affichage des N nombres dans les colonnes }
  39. var i : integer;
  40. begin
  41.  writeln('_____________________________________________________');
  42.   for i:= 1 to N do
  43.    write(Tab[i] : 3, ' | ');writeln;
  44.  writeln('_____________________________________________________');
  45. End;
  46. begin
  47.   Remplir(Tab);
  48.   writeln;
  49.   writeln('TABLEAU NON TRIE');
  50.   Affichage(Tab);
  51.   Tri_bulles(Tab,n);
  52.   writeln;
  53.   writeln('TABLEAU TRIE');
  54.   Affichage(Tab);
  55.   readln;
  56. end.

Friendly, J.P
Title: Re: Can bubble sort be implemented recursively?
Post by: Thaddy on June 10, 2021, 03:26:51 pm
It is more of a stone than a bubble ;), but anyway ...
Whu didn't you use swap() it is in system.
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov on June 10, 2021, 03:38:07 pm
It is more of a stone than a bubble ;), but anyway ...
Whu didn't you use swap() it is in system.
I don't know why, maybe because I was in "homework" mode... it looks a bit more educational that way...
Title: Re: Can bubble sort be implemented recursively?
Post by: simone on June 10, 2021, 04:42:15 pm
As far as I understand, 'swap' does not exchange the value of two variables, as required in the implementation of the bubblesort algorithm (see https://www.freepascal.org/docs-html/rtl/system/swap.html).
Title: Re: Can bubble sort be implemented recursively?
Post by: Thaddy on June 10, 2021, 04:49:34 pm
As far as I understand, 'swap' does not exchange the value of two variables, as required in the implementation of the bubblesort algorithm (see https://www.freepascal.org/docs-html/rtl/system/swap.html).
Yes it does. It swaps lo ()and hi() . e.g. So  to swap two integers you pass a int64
Title: Re: Can bubble sort be implemented recursively?
Post by: simone on June 10, 2021, 04:59:04 pm
Ok, but the values ​​of the two 32bit variables to be exchanged must first be placed in the int64 to be passed as a parameter to 'swap' and then fetched to be written again to the variables. Isn't the classic swap implemented with temporary variable simpler?
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov on June 10, 2021, 05:21:42 pm
As far as I understand, 'swap' does not exchange the value of two variables, as required in the implementation of the bubblesort algorithm (see https://www.freepascal.org/docs-html/rtl/system/swap.html).

I feel a bit confused thinking that swap() is some kind of overloaded function or stl generic for swapping variables. It can be added, of course:
Code: Pascal  [Select][+][-]
  1. {$mode delphi}
  2.  
  3. procedure swap<T>(var a, b: T);
  4. var x: T;
  5. begin
  6.   x := a; a := b; b := x;
  7. end;
  8.   ...
  9.   swap<Integer>(a, b);
  10.  

Ok, but the values ​​of the two 32bit variables to be exchanged must first be placed in the int64 to be passed as a parameter to 'swap' and then fetched to be written again to the variables. Isn't the classic swap implemented with temporary variable simpler?
IMHO, using swap() is a much more complicated ...
Title: Re: Can bubble sort be implemented recursively?
Post by: simone on June 10, 2021, 05:48:05 pm
Quote
IMHO, using swap() is a much more complicated ...

I agree. Your implementation is simple and as general as possible. Just a remark: since it uses a generic freestanding procedure, it requires FPC 3.2.0+.
Title: Re: Can bubble sort be implemented recursively?
Post by: mas steindorff on June 10, 2021, 06:12:18 pm
IMHO, using swap() is a much more complicated ...
Agreed! "swap" has too many implementations across languages ranging from high <=> low byte swap of a word up to full matrices (2d array) exchanges.  I would avoid the plan "swap" keyword and either role your own like "y.ivanov" does or use a different keyword. 
Title: Re: Can bubble sort be implemented recursively?
Post by: BobDog on June 11, 2021, 12:54:40 am

An implementation of some of the ideas.
Code: Pascal  [Select][+][-]
  1. program bsort;
  2. {$mode delphi}
  3.  
  4.  
  5. procedure swap<T>(var a, b: T);
  6. var temp: T;
  7. begin
  8.   temp := a; a := b; b := temp;
  9. end;
  10.  
  11. procedure bubbleSort<T>(var arr:array of T;n:integer);
  12. var
  13. i:integer;
  14. begin
  15.     if (n = 1) then exit;
  16.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then swap<T>(arr[i], arr[i+1]);
  17.     bubbleSort<T>(arr, n-1);
  18. end;
  19.  
  20.  
  21.  
  22.   var n:integer;
  23.   var I:array of integer;
  24.   var s:array of string;
  25.  
  26.   begin
  27.   I:=[6,3,-5,4,2,90,45];
  28.   s:=['k','q','a','u','o'];
  29.  
  30.   bubblesort<integer>(I,7);
  31.   bubblesort<string>(s,5);
  32.  
  33. for n:=0 to 6 do write(I[n],' ');
  34. writeln;
  35. for n:=0 to 4 do write(s[n],' ');
  36. writeln;  
  37.   readln;
  38.   end.
  39.  
  40.  
Title: Re: Can bubble sort be implemented recursively?
Post by: Mr.Madguy on June 11, 2021, 05:26:36 am
Recursion is nothing more, than branching cycle. If there is only one branch at each step - recursion isn't needed and can be replaced by ordinal cycle. Don't overcomplicate things.
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov on June 11, 2021, 11:59:27 am
@BobDog
Good point for to n-2 correction to my blind C translation! Considering argument n as the size of the array, it is the correct loop boundary. If we consider n as the last array index, we should change the stop condition to if (n < 1) otherwise two element arrays won't be sorted.

Recursion is nothing more, than branching cycle. If there is only one branch at each step - recursion isn't needed and can be replaced by ordinal cycle. Don't overcomplicate things.

One can argue the recursion is everything. But that is on theory. :)
Perhaps the complication comes from that it is a school assignment. Who else will care about the bubblesort anyway.
Title: Re: Can bubble sort be implemented recursively?
Post by: Jurassic Pork on June 11, 2021, 01:34:38 pm
hello,
using BobDog algorithm with generics in $Mode objfpc  :
Code: Pascal  [Select][+][-]
  1. program bubbleSort;
  2. {$mode objfpc}
  3. const N = 100;  {Limite supérieure de tableau}
  4. type TTab = array [1..N] of integer;   { TTab : Type Tableau }
  5. var Tab : TTab ;
  6. generic procedure swap<T>(var a, b: T);
  7. var temp: T;
  8. begin
  9.   temp := a; a := b; b := temp;
  10. end;
  11.  
  12. generic procedure fpbubbleSort<T>(var arr:array of T;n:integer);
  13. var
  14. i:integer;
  15. begin
  16.     if (n = 1) then exit;
  17.     for i:=0 to n-2 do if (arr[i] > arr[i+1]) then specialize swap<T>(arr[i], arr[i+1]);
  18.     specialize fpbubbleSort<T>(arr, n-1);
  19. end;
  20.  
  21. procedure Fill(var Tab:TTab) ;
  22. var i : integer;  { i : Indice de tableau de N colonnes }
  23. begin
  24.  Randomize;
  25.  for i := 1 to N do
  26.   tab[i]:=random(N+1);
  27. end;
  28. procedure Display(Tab:TTab) ;
  29. { Affichage des N nombres dans les colonnes }
  30. var i : integer;
  31. begin
  32.  writeln('_____________________________________________________');
  33.   for i:= 1 to N do
  34.    write(Tab[i] : 3, ' | ');writeln;
  35.  writeln('_____________________________________________________');
  36. End;
  37. begin
  38.   Fill(Tab);
  39.   writeln;
  40.   writeln('TABLEAU NON TRIE');
  41.   Display(Tab);
  42.   specialize fpbubbleSort<integer>(Tab,n);
  43.   writeln;
  44.   writeln('TABLEAU TRIE');
  45.   Display(Tab);
  46.   readln;
  47. end.

Result in Attachment

Friendly, J.P
Title: Yes.
Post by: Spoonhorse on June 11, 2021, 02:30:53 pm
As can everything else that can be done in a while loop.

Procedure A:

Code: Pascal  [Select][+][-]
  1. procedure while_loop(var AThing:TThing);
  2. begin
  3. while not end_state(AThing) do
  4.     one_step(AThing);
  5. end;

Procedure B:

Code: Pascal  [Select][+][-]
  1. procedure recursive(var AThing:TThing);
  2. begin
  3. if end_state(AThing) then Exit;
  4. one_step(AThing);
  5. recursive(AThing);
  6. end;
Title: Re: Can bubble sort be implemented recursively?
Post by: Thaddy on June 11, 2021, 02:40:21 pm
One can argue the recursion is everything. But that is on theory. :)
No it is not.
Bubble sorts are usualy faster on very small sorts.(e.g. 2..10)
Most other sorts need to maintain state. A bubblesort does not have state.
Besides: it requires less code.
Title: Re: Can bubble sort be implemented recursively?
Post by: lucamar on June 11, 2021, 03:07:22 pm
Bubble sorts are usualy faster on very small sorts.(e.g. 2..10)
Most other sorts need to maintain state. A bubblesort does not have state.
Besides: it requires less code.

And it's very, very easy to both: understand how it works and code one ;)
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov on June 11, 2021, 03:50:37 pm
One can argue the recursion is everything. But that is on theory. :)
No it is not.
There are functional programming languages (Scheme, Haskell, Erlang) where the loops are explicitly forbidden. So the iteration must be expressed with a tail recursion.

Bubble sorts are usualy faster on very small sorts.(e.g. 2..10)
Most other sorts need to maintain state. A bubblesort does not have state.
Besides: it requires less code.

Allow me to politely disagree with that. Bubblesort is probably one of the worst sorting methods, no matter of the initial conditions. The method worse than bubblesort I can think of is to permute the array and to check if it is ordered. Or maybe to shuffle it randomly until it become in order.

IMHO, In "small sorts" I would prefer the straight selection sort. It is also very easy to write.
Title: Re: Can bubble sort be implemented recursively?
Post by: Mr.Madguy on June 11, 2021, 04:34:15 pm
One can argue the recursion is everything. But that is on theory. :)
Perhaps the complication comes from that it is a school assignment. Who else will care about the bubblesort anyway.
Yeah, but sometimes new programmers are taught wrong way. They're taught to use some "buzzword" technologies, where they're overkill. Recursion is one of them. 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. It's only needed in case of branching cycle - i.e. tree traversal. In case of single branch cycle nothing is needed to be stored as no moving to previous level is needed. Therefore simple cycle should be used in this case, that is much more faster and requires lesser amount of memory. It's ok to use recursion for 10 array elements. But how about 1000? Or 1000000?
Title: Re: Can bubble sort be implemented recursively?
Post by: BobDog on June 11, 2021, 05:07:00 pm

I reckon the opposite applies to quicksort, you cannot quicksort without recursion unless you make a pseudo stack which slows it right down, which defeats the purpose of quicksort.

 Question for Jurrasic pork??

Why do you use
generic procedure fpbubbleSort<T>
and
 specialize fpbubbleSort<T>
when templating the sort.

Is generic needed?
is specialize needed?
Title: Re: Can bubble sort be implemented recursively?
Post by: Jurassic Pork on June 11, 2021, 05:23:29 pm
Question for Jurrasic pork??

Why do you use
generic procedure fpbubbleSort<T>
and
 specialize fpbubbleSort<T>
when templating the sort.

Is generic needed?
is specialize needed?
the syntax in not the same in delphi mode and objfpc mode for generics. I am not sure that my syntax for objfpc  is the best  but the code can be compiled and works.

Friendly, J.P
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov on June 11, 2021, 06:16:13 pm
One can argue the recursion is everything. But that is on theory. :)
Perhaps the complication comes from that it is a school assignment. Who else will care about the bubblesort anyway.
Yeah, but sometimes new programmers are taught wrong way.
I guess that in the OP case the teacher said: "OK, you know what the iteration is, you know bubblesort, you know what the recursion is. Let's see if you can put a recursion into...". Something like that.

They're taught to use some "buzzword" technologies, where they're overkill. Recursion is one of them.
I disagree with the "buzzword". Recursion is a term in computability theory (and also in mathematics). Functional programming is strongly dependent on it.

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)

It's only needed in case of branching cycle - i.e. tree traversal. In case of single branch cycle nothing is needed to be stored as no moving to previous level is needed. Therefore simple cycle should be used in this case, that is much more faster and requires lesser amount of memory. It's ok to use recursion for 10 array elements. But how about 1000? Or 1000000?

And perhaps the next lesson should be: "With iterative and recursive bubblesoft at hand, let's see how big arrays any of them can process until error 202 pops up." :)

BTW, there are elegant recursive algorithms, e.g. the one for parsing pascal sources.

I reckon the opposite applies to quicksort, you cannot quicksort without recursion unless you make a pseudo stack which slows it right down, which defeats the purpose of quicksort.
*snip*
I don't think the pseudo stack slows down the iterative quicksort, the partition boundaries are saved in both cases in stack (machine or pseudo), but the iterative version doesn't perform a call and the stack frame book-keeping. So it is lighter, in fact.
Title: Re: Can bubble sort be implemented recursively?
Post by: Jurassic Pork on June 11, 2021, 06:34:22 pm
in attachment comparison of iterative vs recursive bubblesort using java
Title: Re: Can bubble sort be implemented recursively?
Post by: 440bx on June 11, 2021, 07:26:09 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>
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov 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.
Title: Re: Can bubble sort be implemented recursively?
Post by: 440bx 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.
Title: Re: Can bubble sort be implemented recursively?
Post by: Jurassic Pork 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
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov 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.
Title: Re: Can bubble sort be implemented recursively?
Post by: y.ivanov 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 🍺
Title: Re: Can bubble sort be implemented recursively?
Post by: Jurassic Pork 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
Title: Re: Can bubble sort be implemented recursively?
Post by: BobDog 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.  
Title: Re: Can bubble sort be implemented recursively?
Post by: PascalDragon 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