[…] 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).
Can bubble sort be implemented recursively?
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...It is more of a stone than a bubble ;), but anyway ...Whu didn't you use swap() it is in system.
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
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).
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 ...
IMHO, using swap() is a much more complicated ...
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.
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. :)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.
There are functional programming languages (Scheme, Haskell, Erlang) where the loops are explicitly forbidden. So the iteration must be expressed with a tail recursion.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.
One can argue the recursion is everything. But that is on theory. :)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?
Perhaps the complication comes from that it is a school assignment. Who else will care about the bubblesort anyway.
Question for Jurrasic pork??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.
Why do you use
generic procedure fpbubbleSort<T>
and
specialize fpbubbleSort<T>
when templating the sort.
Is generic needed?
is specialize needed?
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.One can argue the recursion is everything. But that is on theory. :)Yeah, but sometimes new programmers are taught wrong way.
Perhaps the complication comes from that it is a school assignment. Who else will care about the bubblesort anyway.
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?
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.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.
*snip*
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.
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.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.
Recursive BubbleSort time : 0,00734958892067424
Iterative BubbleSort time : 0,0137503988494744
Considering the fact we're talking about something with purely educational purpose, what is actualy "the standard bubblesort"?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.BTW, the probability for the array to be sorted is so small that it merely can't affect its overall quadratic complexity.
hello,It seems that there is an error in rosettacode example. The correct one must be:
here is a console app with recursive and iterative bubblesort algorithms. EpikTimer is used to measure performance.
*snip*
example of result for N=1000 :I haven't used the EpikTimer, but it seems that elapsed time for iterative is added to the previous.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
Recursive BubbleSort time : 0,00012263134358643
Iterative BubbleSort time : 0,0000840197076941564
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)