Can bubble sort be implemented recursively? lazarus / 21-General ---------------------------------------------------------------------- ankitdixit · 2021-06-10 08:10 Hello All, I want to know, Can bubble sort be implemented recursively? If yes, Can anyone expalin this with some examples? ---------------------------------------------------------------------- Kays · 2021-06-10 08:40 Quote from: ankitdixit on June 10, 2021, 10:10:15 am[…] Can bubble sort be implemented recursively?Certainly it can be. Quote from: ankitdixit on June 10, 2021, 10:10:15 amIf yes, Can anyone expalin this with some examples?Yes, anyone can do this with “examples” (aka homework solution). ---------------------------------------------------------------------- Zvoni · 2021-06-10 09:24 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] ---------------------------------------------------------------------- ankitdixit · 2021-06-10 10:12 Hey thanks! I am also found this information on geeksforgeeks and Interviewbit 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 arr[i+1])             {              swap(arr, arr[i+1]);             }         }         // recursion for remaining elements in array         recursiveBubbleSort(arr, n-1);     } ---------------------------------------------------------------------- Zvoni · 2021-06-10 10:14 Your point? ---------------------------------------------------------------------- cdbc · 2021-06-10 10:22 Hi C# is the easiest to translate to pascal  Regards Benny ---------------------------------------------------------------------- alpine · 2021-06-10 12:30 It is more of a stone than a bubble , but anyway ... The C function Code: C  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i void bubbleSort(int arr[], int 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 (int i=0; i arr[i+1])            swap(arr[i], arr[i+1]);     // Largest element is fixed,    // recur for remaining array    bubbleSort(arr, n-1);} should be translated to something like: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure BubbleSort(A: array of Integer; N: Integer);var  I, tmp: Integer;begin  if N = 1 then    Exit;  for I := 0 to N-1 do    if A[I] > A[I+1] then    begin      tmp := A[I]; A[I] := A[I+1]; A[I+1] := tmp;    end;  BubbleSort(A, N-1);end; QuoteCan 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. ---------------------------------------------------------------------- Jurassic Pork · 2021-06-10 12:54 hello, one solution (sorry in french) : Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program bubbleSort;const N = 100;  {Limite supérieure de tableau}type TTab = array [1..N] of integer;   { TTab : Type Tableau }var Tab : TTab ;Procedure Tri_bulles (var t : TTab; n : integer);Var i, aux : integer;    Function Trier (t : TTAB; n : integer) : Boolean;    Var ok : boolean; i : integer;    Begin         ok := true; i := 1;       Repeat               If t[i + 1] < t[i] Then ok := false             Else i := i + 1;         Until ((Not ok) or (i >= n));         Trier := ok;    End;    Begin         If Not Trier (t, n) Then         Begin              For i := 1 To n - 1 Do                If t[i] > t[i + 1] Then                   Begin                        aux := t[i];                        t[i] := t[i + 1];                        t[i + 1] := aux;                   End;              Tri_bulles (t, n);         End;    End;procedure Remplir(var Tab:TTab) ;var i : integer;  { i : Indice de tableau de N colonnes }begin Randomize; for i := 1 to N do  tab[i]:=random(N+1);end;procedure Affichage(Tab:TTab) ;{ Affichage des N nombres dans les colonnes }var i : integer;begin wr iteln('_____________________________________________________');  for i:= 1 to N do   write(Tab[i] : 3, ' | ');writeln; writeln('___________ __________________________________________');End;begin  Remplir(Tab);  writeln;  writeln('TABLEAU NON TRIE');  Affichage(Tab);  Tri_bulles(Tab,n);  writeln;  writeln('TABLEAU TRIE');  Affichage(Tab);  readln;end. Friendly, J.P ---------------------------------------------------------------------- Thaddy · 2021-06-10 13:26 Quote from: y.ivanov on June 10, 2021, 02:30:09 pmIt is more of a stone than a bubble , but anyway ... Whu didn't you use swap() it is in system. ---------------------------------------------------------------------- alpine · 2021-06-10 13:38 Quote from: Thaddy on June 10, 2021, 03:26:51 pmQuote from: y.ivanov on June 10, 2021, 02:30:09 pmIt 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... ---------------------------------------------------------------------- simone · 2021-06-10 14:42 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). ---------------------------------------------------------------------- Thaddy · 2021-06-10 14:49 Quote from: simone on June 10, 2021, 04:42:15 pmAs 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 ---------------------------------------------------------------------- simone · 2021-06-10 14:59 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? ---------------------------------------------------------------------- alpine · 2021-06-10 15:21 Quote from: simone on June 10, 2021, 04:42:15 pmAs 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$mode delphi} procedure swap(var a, b: T);var x: T;begin  x := a; a := b; b := x;end;   ...  swap(a, b);  Quote from: simone on June 10, 2021, 04:59:04 pmOk, 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 ... ---------------------------------------------------------------------- simone · 2021-06-10 15:48 QuoteIMHO, 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+. ---------------------------------------------------------------------- mas steindorff · 2021-06-10 16:12 Quote from: y.ivanov on June 10, 2021, 05:21:42 pmIMHO, 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. ---------------------------------------------------------------------- BobDog · 2021-06-10 22:54 An implementation of some of the ideas. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program bsort;{$mode delphi}  procedure swap(var a, b: T);var temp: T;begin  temp := a; a := b; b := temp;end; procedure bubbleSort(var arr:array of T;n:integer);vari:integer;begin    if (n = 1) then exit;    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then swap(arr[i], arr[i+1]);    bubbleSort(arr, n-1);end;     var n:integer;  var I:array of integer;  var s:array of string;   begin  I:=[6,3,-5,4,2,90,45];  s:=['k','q','a','u','o'];   bubblesort(I,7);  bubblesort(s,5); for n:=0 to 6 do write(I[n],' ');writeln;for n:=0 to 4 do write(s[n],' ');writeln;    readln;  end. ---------------------------------------------------------------------- Mr.Madguy · 2021-06-11 03:26 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. ---------------------------------------------------------------------- alpine · 2021-06-11 09:59 @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. Quote from: Mr.Madguy on June 11, 2021, 05:26:36 amRecursion 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. ---------------------------------------------------------------------- Jurassic Pork · 2021-06-11 11:34 hello, using BobDog algorithm with generics in $Mode objfpc  : Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program bubbleSort;{$mode objfpc}const N = 100;  {Limite supérieure de tableau}type TTab = array [1..N] of integer;   { TTab : Type Tableau }var Tab : TTab ;generic procedure swap(var a, b: T);var temp: T;begin  temp := a; a := b; b := temp;end; generic procedure fpbubbleSort(var arr:array of T;n:integer);vari:integer;begin    if (n = 1) then exit;    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then specialize swap(arr[i], arr[i+1]);    specialize fpbubbleSort(arr, n-1);end; procedure Fill(var Tab:TTab) ;var i : integer;  { i : Indice de tableau de N colonnes }begin Randomize; for i := 1 to N do  tab[i]:=random(N+1);end;procedure Display(Tab:TTab) ;{ Affichage des N nombres dans les colonnes }var i : integer;begin write ln('_____________________________________________________');  for i:= 1 to N do   write(Tab[i] : 3, ' | ');writeln; writeln('_______________ ______________________________________');End;begin  Fill(Tab);  writeln;  writeln('TABLEAU NON TRIE');  Display(Tab);  specialize fpbubbleSort(Tab,n);  writeln;  writeln('TABLEAU TRIE');  Display(Tab);  readln;end. Result in Attachment Friendly, J.P ---------------------------------------------------------------------- Spoonhorse · 2021-06-11 12:30 As can everything else that can be done in a while loop. Procedure A: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure while_loop(var AThing:TThing);beginwhile not end_state(AThing) do    one_step(AThing);end; Procedure B: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure recursive(var AThing:TThing);beginif end_state(AThing) then Exit;one_step(AThing);recursive(AThing);end; ---------------------------------------------------------------------- Thaddy · 2021-06-11 12:40 Quote from: y.ivanov on June 11, 2021, 11:59:27 amOne 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. ---------------------------------------------------------------------- lucamar · 2021-06-11 13:07 Quote from: Thaddy on June 11, 2021, 02:40:21 pmBubble 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 ---------------------------------------------------------------------- alpine · 2021-06-11 13:50 Quote from: Thaddy on June 11, 2021, 02:40:21 pmQuote from: y.ivanov on June 11, 2021, 11:59:27 amOne 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. Quote from: Thaddy on June 11, 2021, 02:40:21 pmBubble 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. ---------------------------------------------------------------------- Mr.Madguy · 2021-06-11 14:34 Quote from: y.ivanov on June 11, 2021, 11:59:27 amOne 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? ---------------------------------------------------------------------- BobDog · 2021-06-11 15:07 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 and  specialize fpbubbleSort when templating the sort. Is generic needed? is specialize needed? ---------------------------------------------------------------------- Jurassic Pork · 2021-06-11 15:23 Quote from: BobDog on June 11, 2021, 05:07:00 pm Question for Jurrasic pork?? Why do you use generic procedure fpbubbleSort and  specialize fpbubbleSort 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 ---------------------------------------------------------------------- alpine · 2021-06-11 16:16 Quote from: Mr.Madguy on June 11, 2021, 04:34:15 pmQuote from: y.ivanov on June 11, 2021, 11:59:27 amOne 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. Quote from: Mr.Madguy on June 11, 2021, 04:34:15 pmThey'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. Quote from: Mr.Madguy on June 11, 2021, 04:34:15 pmIt 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) Quote from: Mr.Madguy on June 11, 2021, 04:34:15 pmIt'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. Quote from: BobDog on June 11, 2021, 05:07:00 pmI 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. ---------------------------------------------------------------------- Jurassic Pork · 2021-06-11 16:34 in attachment comparison of iterative vs recursive bubblesort using java ---------------------------------------------------------------------- 440bx · 2021-06-11 17:26 Quote from: y.ivanov on June 11, 2021, 03:50:37 pmBubblesort 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... ---------------------------------------------------------------------- alpine · 2021-06-11 17:47 Quote from: 440bx on June 11, 2021, 07:26:09 pmQuote from: y.ivanov on June 11, 2021, 03:50:37 pmBubblesort 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... You're probably talking about the improved bubblesort variant which checks whether the last pass was without swaps and if so then finishes. ---------------------------------------------------------------------- 440bx · 2021-06-11 19:05 Quote from: y.ivanov on June 11, 2021, 07:47:23 pmYou'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. ---------------------------------------------------------------------- Jurassic Pork · 2021-06-12 09:07 hello, here is a console app with recursive and iterative bubblesort algorithms. EpikTimer is used to measure performance. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program bubbleSort;{$mode objfpc}uses sysutils,epiktimer,etpackage;const N = 1000;  {Limite supérieure de tableau}type TTab = array  of integer;   { TTab : Type Tableau }var TabSrc,TabTest : TTab ; generic procedure swap(var a, b: T);var temp: T;begin  temp := a; a := b; b := temp;end; generic procedure recursiveBubbleSort(var arr:array of T;n:integer);vari:integer;begin    if (n = 1) then exit;    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then specialize swap(arr[i], arr[i+1]);    specialize recursiveBubbleSort(arr, n-1);end; procedure IterativeBubbleSort(var list: TTab;n:integer);var  i, j: integer;  t: integer;begin  for i := n downto 2 do    for j := 0 to i - 1 do      if list[j] > list[j + 1] then      begin        t := list[j];        list[j] := list[j + 1];        list[j + 1] := t;      end;end; procedure Fill(var Tab:TTab) ;var i : integer;  { i : Indice de tableau de N colonnes }begin Randomize; for i := 1 to N do  tab[i]:=random(N+1);end;procedure Display(Tab:TTab) ;{ Affichage des N nombres dans les colonnes }var i : integer;begin writeln('____________ _________________________________________');  for i:= 1 to N do   write(Tab[i] : 3, ' | ');writeln; writeln('__________________________ ___________________________');End;var    cStart, cStop: Cardinal;     ET: TEpikTimer;       ResIterative, ResRecursive: Extended;begin  ET := TEpikTimer.Create(nil);  ET.Clear;  setLength(TabSrc,N);  Fill(TabSrc);  TabTest := Copy(TabSrc,0,N);  writeln;  writeln('Unsorted Array');  Display(TabTest);  ET.Start;  specialize recursiveBubbleSort(TabTest,n);  ET.Stop;  ResRecursive := ET.elapsed;  writeln;  writeln('Sorted Array with Recursive BubbleSort');  Display(TabTest);  TabTest := Copy(TabSrc,0,N);  ET.Start;  iterativeBubbleSort(TabTest,n);  ET.Stop;  ResIterative := ET.elapsed;  writeln;  writeln('Sorted Array with Iterative BubbleSort');  Display(TabTest);  Writeln('Recursive BubbleSort time : ' + FloatToStr(ResRecursive));  Writeln('Iterative BubbleSort time : ' + FloatToStr(ResIterative));  ET.Free;  readln;end. example of result for N=1000 : QuoteRecursive 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 ---------------------------------------------------------------------- alpine · 2021-06-12 09:20 Quote from: 440bx on June 11, 2021, 09:05:22 pmQuote from: y.ivanov on June 11, 2021, 07:47:23 pmYou'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. Quote from: 440bx on June 11, 2021, 09:05:22 pmif 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. ---------------------------------------------------------------------- alpine · 2021-06-12 12:01 Quote from: Jurassic Pork on June 12, 2021, 11:07:52 amhello, 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure IterativeBubbleSort(var list: TTab;n:integer);var  i, j: integer;  t: integer;begin  for i := n-1 downto 1 do    for j := 0 to i - 1 do    if list[j] > list[j + 1] then      begin        t := list[j];        list[j] := list[j + 1];        list[j + 1] := t;      end;end; Quote from: Jurassic Pork on June 12, 2021, 11:07:52 amexample of result for N=1000 : QuoteRecursive BubbleSort time : 0,00734958892067424 Iterative BubbleSort time : 0,0137503988494744I haven't used the EpikTimer, but it seems that elapsed time for iterative is added to the previous.  Quote from: Jurassic Pork on June 12, 2021, 11:07:52 amyou 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i generic procedure recursiveBubbleSort(var arr:array of T;n:integer);vari:integer; chg: boolean = false;begin    if (n = 1) then exit;    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then begin    specialize swap(arr[i], arr[i+1]); chg := true;    end;    if chg then specialize recursiveBubbleSort(arr, n-1);end; procedure IterativeBubbleSort(var list: TTab;n:integer);var  i, j: integer;  t: integer; chg: boolean = true;begin  {for} i := n - 1; {downto} while (i >= 1) and chg do  begin chg := false;    for j := 0 to i - 1 do    if list[j] > list[j + 1] then      begin        t := list[j];        list[j] := list[j + 1];        list[j + 1] := t; chg := true;      end;    dec(i);  end;end; Cheers 🍺 ---------------------------------------------------------------------- Jurassic Pork · 2021-06-12 12:35 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i for i:= 1 to N do   => Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i for i:= 0 to N-1 do  New code : Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program bubbleSort;{$mode objfpc}uses sysutils,epiktimer,etpackage;const N = 1000;  {Limite supérieure de tableau}type TTab = array  of integer;   { TTab : Type Tableau }var TabSrc,TabTest : TTab ; generic procedure swap(var a, b: T);var temp: T;begin  temp := a; a := b; b := temp;end; generic procedure recursiveBubbleSort(var arr:array of T;n:integer);vari:integer; chg: boolean = false;begin    if (n = 1) then exit;    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then begin    specialize swap(arr[i], arr[i+1]); chg := true;    end;    if chg then specialize recursiveBubbleSort(arr, n-1);end; procedure IterativeBubbleSort(var list: TTab;n:integer);var  i, j: integer;  t: integer; chg: boolean = true;begin  {for} i := n - 1; {downto} while (i >= 1) and chg do  begin chg := false;    for j := 0 to i - 1 do    if list[j] > list[j + 1] then      begin        t := list[j];        list[j] := list[j + 1];        list[j + 1] := t; chg := true;      end;    dec(i);  end;end;  procedure Fill(var Tab:TTab) ;var i : integer;  { i : Indice de tableau de N colonnes }begin Randomize; for i := 0 to N-1 do  tab[i]:=random(N+1);end; procedure Display(Tab:TTab) ;{ Affichage des N nombres dans les colonnes }var i : integer;begin wr iteln('_____________________________________________________');  for i:= 0 to N-1 do   write(Tab[i] : 3, ' | ');writeln; writeln('_________ ____________________________________________');End;var    cStart, cStop: Cardinal;       ET: TEpikTimer;       ResIterative, ResRecursive: Extended;begin  ET := TEpikTimer.Create(nil);  ET.Clear;  setLength(TabSrc,N);  Fill(TabSrc);  TabTest := Copy(TabSrc,0,N);  writeln;  writeln('Unsorted Array');  Display(TabTest);  ET.Start;  specialize recursiveBubbleSort(TabTest,n);  ET.Stop;  ResRecursive := ET.elapsed;  writeln;  writeln('Sorted Array with Recursive BubbleSort');  Display(TabTest);  TabTest := Copy(TabSrc,0,N);  ET.Clear;  ET.Start;  iterativeBubbleSort(TabTest,n);  ET.Stop;  ResIterative := ET.elapsed;  writeln;  writeln('Sorted Array with Iterative BubbleSort');  Display(TabTest);  Writeln('Recursive BubbleSort time : ' + FloatToStr(ResRecursive));  Writeln('Iterative BubbleSort time : ' + FloatToStr(ResIterative));  ET.Free;  readln;end. Result for N= 100 : QuoteRecursive BubbleSort time : 0,00012263134358643 Iterative BubbleSort time : 0,0000840197076941564 Friendly, J.P ---------------------------------------------------------------------- BobDog · 2021-06-12 16:14 Very little difference here: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   program comparesorts;{$mode delphi} usesSysUtils,DateUtils; procedure bubbleSortRE(var arr:array of T;n:int32);vari:int32;temp:T;begin  if (n = 1) then exit;    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then    begin    temp:=arr[i];    arr[i]:=arr[i+1];    arr[i+1]:=temp;    end;    bubbleSortRe(arr, n-1);end; procedure bubbleSortIt(var arr:array of T;n:int32);vari:int32;temp:T;beginwhile (n>1) do  begin    for i:=0 to n-2 do if (arr[i] > arr[i+1]) then    begin    temp:=arr[i];    arr[i]:=arr[i+1];    arr[i+1]:=temp;    end;    n:=n-1;   end;end;  function range(f:int32;l:int32):int32;  begin  range:= trunc(random*(l+1-f) ) +f;  end;     const  limit=30000;   var n:int32;  var I :array[0 .. limit] of int32;  var I2:array[0 .. limit] of int32;  var  D1,D2,D3,D4:tdatetime;     begin    randomize;  for n:=0 to limit do    begin  I[n]:=range(0,100000);  I2[n]:=I[n];  end;  writeln('please wait . . .  ',limit+1,' array elements to sort twice ');   D1:=now;  bubblesortre(I,limit-1);  D2:=now;   D3:=now;  bubblesortit(I2,limit-1);  D4:=now;  for n:=0 to 50 do write(I[n],' ');write(' . . . ');writeln;writeln('Time for recursive ', MilliSecondsBetween(D1, D2), ' milliseconds');writeln;for n:=0 to 50 do write(I2[n],' ');write(' . . . ');writeln;writeln('Time for iterative ', MilliSecondsBetween(D3, D4), ' milliseconds');writeln; writeln('Press return to end');   readln;  end. ---------------------------------------------------------------------- PascalDragon · 2021-06-13 10:37 Quote from: y.ivanov on June 11, 2021, 06:16:13 pmQuote from: Mr.Madguy on June 11, 2021, 04:34:15 pmIt 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program ttailop; {$OPTIMIZATION TAILREC} function Factorial(aValue: LongInt): LongInt;   function IntFactorial(aValue: LongInt; aResult: LongInt): LongInt;  begin    if aValue = 0 then      IntFactorial := aResult    else      IntFactorial := IntFactorial(aValue - 1, aResult * aValue);  end; begin  Factorial := IntFactorial(aValue, 1);end; begin  Writeln(Factorial(3));end. The relevant assembly code (note the jump before the .Lj10 label): Code: ASM  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i .section .t ext.n_p$ttailop$_$factorial$longint$$longint_$$_intfactorial$longint$l ongint$$longint,"x"        .balign 16,0x90.globl  P$TTAILOP$_$FACTORIA L$LONGINT$$LONGINT_$$_INTFACTORIAL$LONGINT$LONGINT$$LONGINTP$TTAILOP$_ $FACTORIAL$LONGINT$$LONGINT_$$_INTFACTORIAL$LONGINT$LONGINT$$LONGINT:. Lc6:.seh_proc P$TTAILOP$_$FACTORIAL$LONGINT$$LONGINT_$$_INTFACTORIAL$L ONGINT$LONGINT$$LONGINT# [8] begin        pushq   %rbp.seh_pushreg %rbp.Lc8:.Lc9:        movq    %rsp,%rbp.Lc10:        leaq    -64(%rsp),%rsp.seh_stackalloc 64.seh_endprologue# Var aValue located at rbp-8, size=OS_S32# Var aResult located at rbp-16, size=OS_S32# Var $parentfp located at rbp-24, size=OS_64# Var $result located at rbp-28, size=OS_S32        movq    %rcx,-24(%rbp)        movl    %edx,-8(%rbp)        movl    %r8d,-16(%rbp).Lj7:# [9] if aValue = 0 then        cmpl    $0,-8(%rbp)        je      .Lj8        jmp     .Lj9.Lj8:# [10] IntFactorial := aResult        movl    -16(%rbp),%eax        movl    %eax,-28(%rbp)        jmp     .Lj10.Lj9:# [12] IntFactorial := IntFactorial(aValue - 1, aResult * aValue);        movl    -16(%rbp),%edx        movl    -8(%rbp),%eax        imull   %edx,%eax        movl    -8(%rbp),%edx        leal    -1(%edx),%edx      movq    -24(%rbp),%rcx        movl    %eax,-16(%rbp)        movl  %edx,-8(%rbp)        movq    %rcx,-24(%rbp)        jmp     .Lj7.Lj10:# [13] end;        movl    -28(%rbp),%eax        nop        leaq    (%rbp),%rsp        popq    %rbp        ret.seh_endproc.Lc7:  The following code will not be optimized in that regard however: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function Factorial(aValue: LongInt): LongInt;begin  if aValue = 0 then    Factorial := 1  else    Factorial := Factorial(aValue - 1) * aValue;end; Also FPC 3.3.1 supports open array parameters for tail recursion optimizations: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function SumL(const Values: array of Integer): Integer;   function SumInt(const Values: array of Integer; Res: Integer): Integer;  begin    if Length(Values) = 0 then      SumInt := Res    else      SumInt := SumInt(Values[0..High(Values) - 1], Res + Values[High(Values)]);  end; begin  SumL := SumInt(Values, 0);end;