Sort Method for 5 var's type Integer

[robinrm]

Hello everybody,

I have made a (German) game in Object Pascal names "Kniffel"
It's almoust finished but for my last two procedures need I a method to sord Integer's from the lowest to fastet.

My var's has the name a, b, c, d, e.

Can anyone send me a post or message for that because all that i found in the network is to complicated for me ...

Cheers

PS: Sorry for my bad english

[Bart]

For only 5 variables try the easy bubbelsort algorithm.
I assume they are in an array[1..5] of Integer.
Start at index 1, if index 2 is smaller than index 1, swap 1 and 2.
Proceed to index 2, if index 3 is smaller than index 3, swap 2 and 3
Continue till you'r at index 4.

Now go back top index 1 and start over again.
Repeat this until no more swaps are necessary in a run from 1 to 5.

Something like this (Untested code...)

Code: Pascal  [Select][+][-]

1. var
2.   Arr: Aarray[1..5] of integer;
3.   SwapDone: Boolean;
4.   i, temp: Integer;
5. ...
6.   repeat
7.     SwapDone := False;
8.     for i := 1 to 4 do
9.     begin
10.       if Arr[i+1] < Arr[i] then
11.       begin
12.         temp := Arr[i];
13.         Arr[i] := Arr[i+1];
14.         Arr[i+1] := temp;
15.         SwapDone := True;
16.       end;
17.     end;
18.   until not SwapDone;
19. ...
20.  

Bart

[Leledumbo]

My var's has the name a, b, c, d, e.

Consider learning to use array, as most sorting algorithms operate on it. It's still possible if you use individual variables, but it will be much longer than necessary. Anyway, you may find selection sort to be easier to understand. Basically at each iteration it searches the lowest value for index i, assuming the value at index i as the lowest initially, at index i + 1 to N comparing with the current lowest value and swap it if lower one found.

[Almir.Bispo]

You can make it simple,using Tstringlist class:

Code: Pascal  [Select][+][-]

1. function Sort( a,b,c,d,e:integer):string;
2. var  S:Tstringlist;
3.      output:string;
4. begin
5. S:=Tstringlist.create;
6. //set values to variables and Tstringlist class receive it
7. S.add( inttostr(a) );
8. S.add( inttostr(b) );
9. S.add( inttostr(c) );
10. S.add( inttostr(d) );
11. S.add( inttostr(e) );
12. S.Sorted:=true;
13. output:=S.Text;
14. result:= output;
15. S.free;
16. end;
17. procedure TForm1.Button1Click(Sender: TObject);
18. begin
19.   //how to use it .The length must be controlled
20. showmessage(Sort(12,00,05,03,01));
21. end;    
22.  

[nummer8]

Sorting integers by using a stringlist is error prone.
The sort is done on character instead of value.

Like you mentioned "Length must be controlled"
if you sort( 12, 2, 5, 3, 1) the numbers will be sorted but not the way you want it.
(1,12,2,3,5)

I doubt it if TS is aware of the pitfalls of this method.


Jos

@robinrm
Did you find www.lazarusforum.de this is a lazarusforum in German language.

[howardpc]

For the particular case of sorting an array of unique integers (or sorting an unknown array of integers and completely ignoring any duplicates) there is a very fast technique you can use. Indeed I believe there is no faster way to sort integers. It works by building an array of bits where each bit represents a successive integer value.
You clear the sorting array, so no bits are set initially (in the following implementation the compiler does this for us).
You traverse your other array of integers to sort, setting the corresponding bit in the sorting array.
Then you traverse the array of bits. If you find a bit set you output the corresponding integer value.
An implementation for an array of DWord values follows. It produces virtually instantaneous sorted output even for quite large integer arrays.

Code: Pascal  [Select][+][-]

1. program SortInteger;
2.  
3. {$Mode objfpc}{$H+}
4. {$IfDef windows}{$AppType console}{$EndIf}
5.  
6. type
7.  
8.   TByteDynArray = array of Byte;
9.  
10.   TDWordDynArray = array of DWord;
11.  
12.   function FoundMinMax(aDWordArray: TDWordDynArray; out aMin, aMax: DWord): Boolean;
13.   var
14.     i: DWord;
15.   begin
16.     aMin:=High(DWord);
17.     aMax:=Low(DWord);
18.     for i in aDWordArray do begin
19.       if i > aMax then
20.         aMax:=i
21.       else if i = aMax then  // this detects some duplicates
22.         Exit(False);
23.       if i < aMin then
24.         aMin:=i
25.       else if i = aMin then
26.         Exit(False);
27.     end;
28.     Result:=True;
29.   end;
30.  
31.   procedure DivMod(aDividend, aDivisor: DWord; out aDiv, aMod: DWord);
32.   begin
33.     aDiv:=aDividend div aDivisor;
34.     aMod:=aDividend - (aDiv * aDivisor);
35.   end;
36.  
37.   procedure SetBit(aBitIndex: Byte; var aByte: Byte);
38.   begin
39.     aByte:=aByte or (%1 shl aBitIndex);
40.   end;
41.  
42.   procedure MapToByteArray(aNum: DWord; var aByteArray: TByteDynArray);
43.   var
44.     divved, remainder: DWord;
45.   begin
46.     DivMod(aNum, 8, divved, remainder);
47.     SetBit(remainder, aByteArray[divved]);
48.   end;
49.  
50.   function ArrayOfBitsToNumber(anIndex: Integer; aBit: Byte; aByteArray: TByteDynArray): DWord;
51.   begin
52.     Exit(anIndex shl 3 + aBit);
53.   end;
54.  
55.   function IsArrayBitSet(anIndex: Integer; aBit: Byte; aByteDynArray: TByteDynArray): Boolean;
56.   var
57.     mask: Byte;
58.   begin
59.     mask:=(%1 shl aBit);
60.     Exit(aByteDynArray[anIndex] and mask = mask);
61.   end;
62.  
63. var
64.   sortArray: TByteDynArray;
65.   dwa: TDWordDynArray;
66.   min, max, dw: DWord;
67.   index, bit: Integer;
68. begin
69.   // example array of non-duplicate integral values
70.   dwa:=TDWordDynArray.create(3547, 100, 223, 16, 89, 33, 500, 100, 89);
71.  
72.   if not FoundMinMax(dwa, min, max) then
73.     WriteLn('Integer sequence contains duplicate(s)')
74.   else begin
75.     WriteLn('min=',min,', max=',max);
76.     SetLength(sortArray, max div 8 + 1);
77.     for dw in dwa do
78.       MapToByteArray(dw, sortArray);
79.     min:=min div 8;
80.     for index:=min to High(sortArray) do
81.       for bit:=0 to 7 do
82.         if IsArrayBitSet(index, bit, sortArray) then begin
83.           Writeln(ArrayOfBitsToNumber(index, bit, sortArray));
84.         end;
85.   end;
86.  
87.   ReadLn;
88. end.

[ASerge]

Code: Pascal  [Select][+][-]

1. {$APPTYPE CONSOLE}
2. program Project1;
3.  
4. uses Classes;
5.  
6. var
7.   Bits: TBits;
8.   Num: Integer;
9.   Source: TBoundArray;
10. begin
11.   Source := TBoundArray.Create(3547, 100, 223, 16, 89, 33, 500, 100, 89);
12.   Bits := TBits.Create;
13.   try
14.     for Num in Source do
15.       Bits[Num] := True;
16.     Num := Bits.FindFirstBit(True);
17.     while Num >= 0 do
18.     begin
19.       Writeln(Num);
20.       Num := Bits.FindNextBit;
21.     end;
22.   finally
23.     Bits.Free;
24.   end;
25.   Readln;
26. end.

Source can be console input, without min and max calculation.

[engkin]

Indeed I believe there is no faster way to sort integers.

That's because they are not sorted. Every time we go through the bits we are wasting time to find the next number.

Being lazy, I would like to use generics:
add unit fgl to your uses section:

Code: Pascal  [Select][+][-]

1. uses
2.  ..., fgl:
3.  

Specialize one type:

Code: Pascal  [Select][+][-]

1. type
2.   TIntList = specialize TFPGList<integer>;

use it:

Code: Pascal  [Select][+][-]

1. function compareInt(const Item1, Item2: integer): Integer;
2. begin
3.   Result := Item1-Item2;
4. end;
5.  
6. var
7.   l:TIntList;
8.   i: integer;
9. begin
10.   l := TIntList.Create;
11.   try
12.     l.Add(5);
13.     l.Add(12);
14.     l.Add(2);
15.     l.Add(5);
16.     l.Add(3);
17.     l.Add(1);
18.     l.Sort(@compareInt);
19.     for i := 0 to l.Count-1 do
20.       WriteLn(l[i]);
21.   finally
22.     l.Free;
23.   end;
24.   ReadLn;
25. end.

Nothing like being lazy.

[Thaddy]

Nothing like being lazy.

I totally agree. Have a look at this:

Code: Pascal  [Select][+][-]

1. program sortarray;
2. {$mode delphi}{$MACRO ON}{$IF FPC_FULLVERSION < 30101}{$ERROR NEEDS FPC 3.1.1 or HIGHER}{$ENDIF}
3. uses generics.collections;
4. var
5.   a:TArray<integer>;
6.   i:integer;
7. begin
8.   a :=[3,1,2,5,4];
9.   TArrayHelper<integer>.Sort(a);  // NOTE: This is a class. Not a type helper. Will be renamed/added to Tarray<T> in a future version.
10.   for i in a do writeln(i);
11. end.

That's all (in trunk...) Quite a bit lazier, I guess...

[hnb]

That's all (in trunk...) Quite a bit lazier, I guess...

Trunk is not needed. Latest version from https://github.com/maciej-izak/generics.collections works also with latest stable FPC 3.0.4

[Thaddy]

[Trunk is not needed. Latest version from https://github.com/maciej-izak/generics.collections works also with latest stable FPC 3.0.4

But that takes a separate download? Anyway you did a nice job!

[hnb]

But that takes a separate download? Anyway you did a nice job!

Yes. I was in opposition to including rtl-generics into 3.0.4 (it was considered). So thanks to me we don't have rtl-generics in 3.0.4 and you need to download library on your own .

[ASerge]

Test for "Nothing like being lazy"

Enter size of array (<=0 to end): 5
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 31
SortGeneric elapsed: 16
--------------------
Enter size of array (<=0 to end): 50
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 31
SortGeneric elapsed: 16
--------------------
Enter size of array (<=0 to end): 500
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 47
SortGeneric elapsed: 171
--------------------
Enter size of array (<=0 to end): 5000
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 94
SortGeneric elapsed: 1217
--------------------
Enter size of array (<=0 to end): 50000
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 515
SortGeneric elapsed: 13946
--------------------

[Thaddy]

Test for "Nothing like being lazy"

Did you test my version using  rtl-generics too? should be much faster than fgl....

[hnb]

Did you test my version using  rtl-generics too? should be much faster than fgl....

I did.

Enter size of array (<=0 to end): 5
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 15
SortGeneric elapsed: 0
SortGenericsCollections elapsed: 0
--------------------
Enter size of array (<=0 to end): 50
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 31
SortGeneric elapsed: 32
SortGenericsCollections elapsed: 0
--------------------
Enter size of array (<=0 to end): 500
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 31
SortGeneric elapsed: 109
SortGenericsCollections elapsed: 31
--------------------
Enter size of array (<=0 to end): 5000
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 47
SortGeneric elapsed: 1310
SortGenericsCollections elapsed: 375
--------------------
Enter size of array (<=0 to end): 50000
Enter max integer: 1000
Enter test count: 1000
SortBits elapsed: 406
SortGeneric elapsed: 15163
SortGenericsCollections elapsed: 4524
--------------------