Sorting an array?

[Jay]

Doe FP have a unit which contains procedures for sorting arrays? I couldn't find anything in the docs. I know it's easy enough to write your own from scratch but as it's such a common operation I thought there would be a handy routine for it. Thanks.

[Thaddy]

Look at rtl-generics. It has Delphi 2009+ compatible array sorts on any type of array.

[Jay]

Thanks. I haven't got my head around OOP yet so I was looking for something procedural, but useful for future reference.

[Thaddy]

In fact it is procedural, because the TArray<T>.Sort() methods are class methods.

But you can also download 17628 from the embarcadero developers website. That is fully procedural but 32 bit only. It compiles in {$mode delphi}.

[sam707]

you can get inspiration here (dont worry the link below is in english lang)

http://jean-pierre.moreau.pagesperso-orange.fr/p_sort.html

in some cases TRUE QuickSort algo (my favorite) is more efficient than the inplace mergesort implementation in the fcl of Free Pascal that some people call quicksort, but is NOT

[sam707]

I know it's easy enough to write your own from scratch

huh? computer scientists (1980-90) had great times over years and years, starting from scratch to get fast and safe sort algorithms. So I definitively disagree with "easy" LOL

[skalogryz]

Yeah, I posted this old-school approach before.

Well, let me do it again!
Below is AnySort function that can sort any array of any data as long as comparison routine is provided.
SortArrayInteger() is an example of how to sort an array of integers using AnySort.

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

1. unit anysort;
2.  
3. {$ifdef fpc}{$mode delphi}{$H+}{$endif}
4.  
5. interface
6.  
7. type
8.   TCompareFunc = function (const elem1, elem2): Integer;
9.  
10. procedure AnySort(var Arr; Count: Integer; Stride: Integer; CompareFunc: TCompareFunc);
11. procedure SortArrayInteger(var arr: array of Integer; count: Integer);
12.  
13. implementation
14.  
15. type
16.   TByteArray = array [Word] of byte;
17.   PByteArray = ^TByteArray;
18.  
19. procedure AnyQuickSort(var Arr; idxL, idxH: Integer;
20.   Stride: Integer; CompareFunc: TCompareFunc; var SwapBuf);
21. var
22.   ls,hs : Integer;
23.   li,hi : Integer;
24.   mi    : Integer;
25.   ms    : Integer;
26.   pb    : PByteArray;
27. begin
28.   pb:=@Arr;
29.   li:=idxL;
30.   hi:=idxH;
31.   mi:=(li+hi) div 2;
32.   ls:=li*Stride;
33.   hs:=hi*Stride;
34.   ms:=mi*Stride;
35.   repeat
36.     while CompareFunc( pb[ls], pb[ms] ) < 0 do begin
37.       inc(ls, Stride);
38.       inc(li);
39.     end;
40.     while CompareFunc( pb[ms], pb[hs] ) < 0 do begin
41.       dec(hs, Stride);
42.       dec(hi);
43.     end;
44.     if ls <= hs then begin
45.       Move(pb[ls], SwapBuf, Stride);
46.       Move(pb[hs], pb[ls], Stride);
47.       Move(SwapBuf, pb[hs], Stride);
48.       inc(ls, Stride); inc(li);
49.       dec(hs, Stride); dec(hi);
50.     end;
51.   until ls>hs;
52.   if hi>idxL then AnyQuickSort(Arr, idxL, hi, Stride, CompareFunc, SwapBuf);
53.   if li<idxH then AnyQuickSort(Arr, li, idxH, Stride, CompareFunc, SwapBuf);
54. end;
55.  
56. procedure AnySort(var Arr; Count: Integer; Stride: Integer; CompareFunc: TCompareFunc);
57. var
58.   buf: array of byte;
59. begin
60.   SetLength(buf, Stride);
61.   AnyQuickSort(Arr, 0, Count-1, Stride, compareFunc, buf[0]);
62. end;
63.  
64. function CompareInt(const d1,d2): integer;
65. var
66.   i1 : integer absolute d1;
67.   i2 : integer absolute d2;
68. begin
69.   if i1=i2 then Result:=0
70.   else if i1<i2 then Result:=-1
71.   else Result:=1;
72. end;
73.  
74. procedure SortArrayInteger(var arr: array of Integer; count: Integer);
75. begin
76.   AnySort(arr, Count, sizeof(Integer), CompareInt);
77. end;
78.  
79. end.
80.  

and the program

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

1. {$mode delphi}
2. uses anysort;
3.  
4. var
5.   d : array of integer;
6.   a : array of Integer;
7.   i : integer;
8. begin
9.   SetLength(d, 10);
10.   for i:=0 to length(d)-1 do d[i]:=random(200);
11.   SetLength(a, length(d));
12.   for i:=0 to length(a)-1 do a[i]:=d[i];
13.  
14.   for i:=0 to length(d)-1 do
15.     write(d[i],' ');
16.   writeln;
17.   SortArrayInteger(d,length(d));
18.   for i:=0 to length(d)-1 do
19.     write(d[i],' ');
20. end.
21.  

[sam707]

cool mergesort still prefer TRUE qsort, nvm, as long as it works on fast machines, mergesort is ok even if you call it quicksort (that is not)

http://jean-pierre.moreau.pagesperso-orange.fr/Pascal/tqcksrt_pas.txt

[skalogryz]

iirc performance comparison between merge sort and quick sort are the same.
I prefer merge sort, because I remember the algorithm... which I don't for qsort

for merge sort, memory consumption might be an issue, though.
Anyone to rewrite AnySort to quicksort?

[djzepi]

I tested a few sorting algorithms

(in raspberry pi 2)

- Anysort
  0.231 sec

- Radiax Sort (http://wiki.freepascal.org/Radix_sort)
  0.228 sec

- Counting Sort (http://wiki.freepascal.org/Counting_sort)
  0.018 sec

- Smoothsort (http://wiki.freepascal.org/Smoothsort)
  0.568 sec

- Bubble sort (http://wiki.freepascal.org/Bubble_sort)
  4 min 41.306 sec

[BeniBela]

I have an anysort, too ! https://github.com/benibela/bbutils/blob/master/bbutils.pas#L6449-L6616

Though it might be slow?

[howardpc]

Anyone to rewrite AnySort to quicksort?

@skalogryz
Do you mean write AnySort to use MergeSort?
AnySort seems to use quicksort in the implementation you show.

[skalogryz]

um. ok. let's keep it as is then.

The main point of it, is not the performance of sorting, but rather an ability to sort ANY array (w/o need of generics or classes)

[Morton]

Quicksort is easy to implement, recursive or without recursion.
Pro: Few exchanges.
Contra: Lots of comparisons.

Mergesort is quite tricky to implement and a true snail if implemented recursively
Pro: Few  comparisons.
Contra: Lots of exchanges.

For a not to small number of items and with a time consuming comparison eg. lexicaly Mergesort will allways win,
and may be up to ten times faster than Quicksort.

[Thaddy]

Well, the sort that wins is really dependent on the characteristics of the task at hand.
Furthermore it is also dependent on the implementation. E.g. Tail-recursive implementations of any sort algorithm are not always appropriate and can be replaced by  a stack based implementation.
You have to know the time domain and distribution characteristics of your task first, not that of the sort, to apply the best sort.