Recent

Author Topic: Bubblesort  (Read 8502 times)

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
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.... :D My cheeky code works.... and is fast... for a bubblesort... O:-) 8-)
Specialize a type, not a var.

lainz

  • Hero Member
  • *****
  • Posts: 4460
    • https://lainz.github.io/
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

  • Newbie
  • 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...  8-)
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

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
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... :-X 8-)

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 »
Specialize a type, not a var.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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.... :D My cheeky code works.... and is fast... for a bubblesort... O:-) 8-)

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

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.  
  53.   ReadLn;
  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.

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
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  8-) And it is a fun technique  ::) :D :D
« Last Edit: June 20, 2018, 11:44:52 pm by Thaddy »
Specialize a type, not a var.

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • 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

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • 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 < 8) >
Code: Pascal  [Select][+][-]
  1. program champagnesort;
Modern pascal. Adapted from our wiki. Programming with xor swap, saves temp..

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

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

 

TinyPortal © 2005-2018