Recent

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

mas steindorff

  • Sr. Member
  • ****
  • Posts: 455
Re: Can bubble sort be implemented recursively?
« Reply #15 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. 
windows 7/10 - laz 2.0 / 1.2.6 general releases

BobDog

  • Jr. Member
  • **
  • Posts: 78
Re: Can bubble sort be implemented recursively?
« Reply #16 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.  

Mr.Madguy

  • Hero Member
  • *****
  • Posts: 667
Re: Can bubble sort be implemented recursively?
« Reply #17 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.
30.04.2021 - DynamicData 4.0 is released and migration to it is completed.
It's more Lazarus-friendly, but still requires full Delphi 2009 support to be ported to Lazarus.
It's time to finally do it, because Delphi 2009 is 12 years old.

y.ivanov

  • Full Member
  • ***
  • Posts: 132
Re: Can bubble sort be implemented recursively?
« Reply #18 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.

Jurassic Pork

  • Hero Member
  • *****
  • Posts: 974
Re: Can bubble sort be implemented recursively?
« Reply #19 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
« Last Edit: June 11, 2021, 01:41:34 pm by Jurassic Pork »
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

Spoonhorse

  • New Member
  • *
  • Posts: 49
Yes.
« Reply #20 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;
« Last Edit: June 11, 2021, 04:48:20 pm by Spoonhorse »

Thaddy

  • Hero Member
  • *****
  • Posts: 10784
Re: Can bubble sort be implemented recursively?
« Reply #21 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.
« Last Edit: June 11, 2021, 02:42:08 pm by Thaddy »

lucamar

  • Hero Member
  • *****
  • Posts: 4014
Re: Can bubble sort be implemented recursively?
« Reply #22 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 ;)
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

y.ivanov

  • Full Member
  • ***
  • Posts: 132
Re: Can bubble sort be implemented recursively?
« Reply #23 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.

Mr.Madguy

  • Hero Member
  • *****
  • Posts: 667
Re: Can bubble sort be implemented recursively?
« Reply #24 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?
30.04.2021 - DynamicData 4.0 is released and migration to it is completed.
It's more Lazarus-friendly, but still requires full Delphi 2009 support to be ported to Lazarus.
It's time to finally do it, because Delphi 2009 is 12 years old.

BobDog

  • Jr. Member
  • **
  • Posts: 78
Re: Can bubble sort be implemented recursively?
« Reply #25 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?

Jurassic Pork

  • Hero Member
  • *****
  • Posts: 974
Re: Can bubble sort be implemented recursively?
« Reply #26 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
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

y.ivanov

  • Full Member
  • ***
  • Posts: 132
Re: Can bubble sort be implemented recursively?
« Reply #27 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.

Jurassic Pork

  • Hero Member
  • *****
  • Posts: 974
Re: Can bubble sort be implemented recursively?
« Reply #28 on: June 11, 2021, 06:34:22 pm »
in attachment comparison of iterative vs recursive bubblesort using java
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

440bx

  • Hero Member
  • *****
  • Posts: 2368
Re: Can bubble sort be implemented recursively?
« Reply #29 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>
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

 

TinyPortal © 2005-2018