### Author Topic: Bubblesort  (Read 2411 times)

• Hero Member
• Posts: 7136
##### Re: Bubblesort
« Reply #15 on: June 20, 2018, 09:09:14 pm »
https://github.com/mish24/Assembly-step-by-step/blob/master/Bubble-sort.asm
Not cross platform.... My cheeky code works.... and is fast... for a bubblesort...
inline variables like in D10.3 are a bit like Brexit: if you are given the wrong information it sounds like a good idea. Every kid loves candy, but it makes you fat and your teeth will disappear.

#### lainz

• Hero Member
• Posts: 2879
##### Re: Bubblesort
« Reply #16 on: June 20, 2018, 09:11:02 pm »
I know =)

Also I must say that is more human readable the Pascal one (at least for me).

#### Beachtante

• New member
• Posts: 6
##### Re: Bubblesort
« Reply #17 on: June 20, 2018, 09:57:54 pm »
I removed another temp. We just crossed... And made it slightly more useful in a thread (by making it a Boolean function). Rather proud of this...
If this was homework, nobody is going to believe Beachtante..... Oh, and of course, it works....

yeah i would rather leave it like that than put ur way in because i dont even nkow most of the terms

• Hero Member
• Posts: 7136
##### Re: Bubblesort
« Reply #18 on: June 20, 2018, 09:59:06 pm »
@Beachtante: Acutally you should know the syntax in the bubbles function itself. Only in the program part I use exotic syntax.
"Improved" code to help a bit. Removed modern syntax:
Code: Pascal  [Select]
1. program champagnesort;
2. {\$mode objfpc}
3. function BubblesSort(var a: array of integer ):boolean;
4. var
5.   i:integer;
6. begin
7.   repeat
8.     Result := true;
9.     for i := Succ(low(a)) to High(a) do
10.       begin
11.         if a[ Pred(i) ] > a[ i ] then // xor swap
12.           begin
13.             a[Pred(i)] := a[Pred(i)] xor a[i];
14.             a[i] := a[Pred(i)] xor a[i];
15.             a[Pred(i)] := a[Pred(i)] xor a[i];
16.             Result := i = 0;
17.           end;
18.       end ;
19.   until Result;
20. end;
21.
22. const
23.   a:array[0..7] of integer = (123123,12,1,55,6686,5,1555,666);
24. var
25.   i:integer;
26. begin
27.   BubblesSort(a);
28.   for  i := 0 to 7 do writeln(a[i]);
29. end.
30.

In some dialects of "classic" pascal this will give you an eleven... Teachers usually are not able to write such code...

But I still recommend to write it like this if it is not homework (and you use trunk!):
Code: Pascal  [Select]
1. program champagnesort;
2. {\$mode objfpc}
3. function BubblesSort(var a: array of integer ):boolean;
4. var
5.   i:integer;
6. begin
7.   repeat
8.     Result := true;
9.     for i := Succ(low(a)) to High(a) do
10.       begin
11.         if a[ Pred(i) ] > a[ i ] then // xor swap
12.           begin
13.             a[Pred(i)] := a[Pred(i)] xor a[i];
14.             a[i] := a[Pred(i)] xor a[i];
15.             a[Pred(i)] := a[Pred(i)] xor a[i];
16.             Result := i = 0;
17.           end;
18.       end ;
19.   until Result;
20. end;
21.
22. var
23.   a:array of integer;
24.   v:integer;
25. begin
26.   a := [123123,12,1,55,6686,5,1555,666]; // modern dynamic array initialization
27.   BubblesSort(a);
28.   for v in a do writeln(v); // modern looping over values without using an index
29. end.

You can even improve it further...(which I saw but this is enough).
« Last Edit: June 20, 2018, 10:30:45 pm by Thaddy »
inline variables like in D10.3 are a bit like Brexit: if you are given the wrong information it sounds like a good idea. Every kid loves candy, but it makes you fat and your teeth will disappear.

#### Zoran

• Hero Member
• Posts: 1278
##### Re: Bubblesort
« Reply #19 on: June 20, 2018, 11:06:54 pm »
https://github.com/mish24/Assembly-step-by-step/blob/master/Bubble-sort.asm
Not cross platform.... My cheeky code works.... and is fast... for a bubblesort...

Actually xor swap is slower than swap with temp. But at least it saves four bytes on the stack.

This programme:
Code: Pascal  [Select]
1. program TestSwaps;
2.
3. uses
4.   SysUtils;
5.
6. type
7.   TSwapType = LongInt;
8.   TSwapProc = procedure(var M, N: TSwapType);
9.
10. procedure TempSwap(var M, N: TSwapType);
11. var
12.   Temp: TSwapType;
13. begin
14.   Temp := M;
15.   M := N;
16.   N := Temp;
17. end;
18.
19. procedure XORSwap(var M, N: TSwapType);
20. begin
21.   M := M xor N;
22.   N := M xor N;
23.   M := M xor N;
24. end;
25.
26. procedure MeasureSwapTime(const Name: String; SwapProc: TSwapProc);
27. const
28.   Iterations = 1000000000;
29. var
30.   I: Integer;
31.   M, N: TSwapType;
32.   StartTime, EndTime: Extended;
33. begin
34.   M := 1;
35.   N := 2;
36.
37.   StartTime := 1.0e-3 * TimeStampToMSecs(DateTimeToTimeStamp(SysUtils.Now));
38.
39.   for I := 1 to Iterations do
40.     SwapProc(M, N);
41.
42.   EndTime := 1.0e-3 * TimeStampToMSecs(DateTimeToTimeStamp(SysUtils.Now));
43.
44.   Write(Iterations, ' calls of ', Name, ' took ');
45.   Write(Format('%.3N', [EndTime - StartTime]));
46.   WriteLn(' seconds.');
47. end;
48.
49. begin
50.   MeasureSwapTime('TempSwap', @TempSwap);
51.   MeasureSwapTime('XORSwap', @XORSwap);
52.
54. end.
55.
56.

Gives these results on my system (Linux Mint 18.3, 64bit)

With -O1:
Quote
1000000000 calls of TempSwap took 5.254 seconds.
1000000000 calls of XORSwap took 8.727 seconds.

With -O2:
Quote
1000000000 calls of TempSwap took 3.071 seconds.
1000000000 calls of XORSwap took 7.570 seconds.

With -O3 (Only XORSwap is better than with -O2):
Quote
1000000000 calls of TempSwap took 3.081 seconds.
1000000000 calls of XORSwap took 5.878 seconds.

With -O4 (no more optimisation here):
Quote
1000000000 calls of TempSwap took 3.060 seconds.
1000000000 calls of XORSwap took 5.891 seconds.

• Hero Member
• Posts: 7136
##### Re: Bubblesort
« Reply #20 on: June 20, 2018, 11:33:00 pm »
@Zoran
It depends on system, but usually an xor swap is slower on intel systems. That's true.
On arm systems it is often faster, though in the sense that on arm the differences seem there, but 20% instead of 50%.
Wikipedia has a neat write up on the xor swap that explains the theory and applicability.
I was just obfuscating  And it is a fun technique
« Last Edit: June 20, 2018, 11:44:52 pm by Thaddy »
inline variables like in D10.3 are a bit like Brexit: if you are given the wrong information it sounds like a good idea. Every kid loves candy, but it makes you fat and your teeth will disappear.

#### VTwin

• Sr. Member
• Posts: 455
• Former Turbo Pascal 3 user
##### Re: Bubblesort
« Reply #21 on: July 11, 2018, 04:01:29 am »
But now im at the point that i cant do it by myself.
Because i am sitting at this already about like 4-6 houers to get this done.
So if somebody have time to help me .I would be very Thankfull.

As a university professor, while impressed by your initiative, I'm not impressed by your integrity or skills. One learns by solving problems on your own, rather than asking others for solutions. I'd give you a failing grade.

No offense to any replies, it is always fun to be presented with a challenge.

Cheers,
VTwin
« Last Edit: July 11, 2018, 04:30:21 am by VTwin »
“Talk is cheap. Show me the code.” Linus Torvalds

Lazarus 1.8.4, FPC 3.0.4
macOS 10.11.5 (32 bit Carbon, working on Cocoa)
Windows 7 (64 bit)
Ubuntu 16.04.3 (64 bit)

#### VTwin

• Sr. Member
• Posts: 455
• Former Turbo Pascal 3 user
##### Re: Bubblesort
« Reply #22 on: July 11, 2018, 04:27:34 am »
Take a good look at the example I gave you. There is another error in your code.
Maybe this helps to obfuscate < >
Code: Pascal  [Select]
1. program champagnesort;
Modern pascal. Adapted from our wiki. Programming with xor swap, saves temp..

“Talk is cheap. Show me the code.” Linus Torvalds

Lazarus 1.8.4, FPC 3.0.4
macOS 10.11.5 (32 bit Carbon, working on Cocoa)
Windows 7 (64 bit)
Ubuntu 16.04.3 (64 bit)