Sorting an array?
lazarus / 62-General

----------------------------------------------------------------------
Jay · 2016-11-28 09:28

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 · 2016-11-28 09:36

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

----------------------------------------------------------------------
Jay · 2016-11-28 10:51

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

----------------------------------------------------------------------
Thaddy · 2016-11-28 12:16

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 · 2016-12-14 15:59

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 · 2016-12-14 16:09

Quote from: Jay on November 28, 2016, 10:28:17 amI 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 · 2016-12-14 16:17

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][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i unit
anysort; {$ifdef fpc}{$mode delphi}{$H+}{$endif} interface type 
TCompareFunc = function (const elem1, elem2): Integer; procedure
AnySort(var Arr; Count: Integer; Stride: Integer; CompareFunc:
TCompareFunc);procedure SortArrayInteger(var arr: array of Integer;
count: Integer); implementation type  TByteArray = array [Word] of
byte;  PByteArray = ^TByteArray; procedure AnyQuickSort(var Arr; idxL,
idxH: Integer;  Stride: Integer; CompareFunc: TCompareFunc; var
SwapBuf);var  ls,hs : Integer;  li,hi : Integer;  mi    : Integer;  ms
   : Integer;  pb    : PByteArray;begin  pb:=@Arr;  li:=idxL; 
hi:=idxH;  mi:=(li+hi) div 2;  ls:=li*Stride;  hs:=hi*Stride; 
ms:=mi*Stride;  repeat    while CompareFunc( pb[ls], pb[ms] ) < 0 do
begin      inc(ls, Stride);      inc(li);    end;    while
CompareFunc( pb[ms], pb[hs] ) < 0 do begin      dec(hs, Stride);     
dec(hi);    end;    if ls <= hs then begin      Move(pb[ls], SwapBuf,
Stride);      Move(pb[hs], pb[ls], Stride);      Move(SwapBuf, pb[hs],
Stride);      inc(ls, Stride); inc(li);      dec(hs, Stride);
dec(hi);    end;  until ls>hs;  if hi>idxL then AnyQuickSort(Arr,
idxL, hi, Stride, CompareFunc, SwapBuf);  if li<idxH then
AnyQuickSort(Arr, li, idxH, Stride, CompareFunc,
SwapBuf);end; procedure AnySort(var Arr; Count: Integer; Stride:
Integer; CompareFunc: TCompareFunc);var  buf: array of byte;begin 
SetLength(buf, Stride);  AnyQuickSort(Arr, 0, Count-1, Stride,
compareFunc, buf[0]);end; function CompareInt(const d1,d2):
integer;var  i1 : integer absolute d1;  i2 : integer absolute
d2;begin  if i1=i2 then Result:=0  else if i1<i2 then Result:=-1  else
Result:=1;end; procedure SortArrayInteger(var arr: array of Integer;
count: Integer);begin  AnySort(arr, Count, sizeof(Integer),
CompareInt);end; end. 
and the program
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i {$mode
delphi}uses anysort; var  d : array of integer;  a : array of
Integer;  i : integer;begin  SetLength(d, 10);  for i:=0 to
length(d)-1 do d[i]:=random(200);  SetLength(a, length(d));  for i:=0
to length(a)-1 do a[i]:=d[i];   for i:=0 to length(d)-1 do   
write(d[i],' ');  writeln;  SortArrayInteger(d,length(d));  for i:=0
to length(d)-1 do    write(d[i],' ');end.

----------------------------------------------------------------------
sam707 · 2016-12-14 16:22

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 · 2016-12-14 16:25

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 · 2016-12-14 19:52

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 · 2016-12-14 21:26

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

Though it might be slow?

----------------------------------------------------------------------
howardpc · 2016-12-14 22:29

Quote from: skalogryz on December 14, 2016, 05:25:56 pmAnyone 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 · 2016-12-15 03:05

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 · 2016-12-19 19:18

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 · 2016-12-19 19:29

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.

----------------------------------------------------------------------
ArtLogi · 2016-12-19 19:38

Isn't these also depending a) memory b) time per cycle c) overall
speed and the best for the task is the one with the best average
features.

I don't know except that basic sort can be done with ladder logic and
people started to yel that my implementation were unefficient since no
bubbles nor snorts.

----------------------------------------------------------------------
jollytall · 2019-12-28 12:40

@skalogryz
I am afraid, the posted algorithm (Same at:
https://wiki.freepascal.org/Array_sort) is wrong.

The original QuickSort uses an arbitrary number (some places call it
"Pivot"), to swap every item that is larger to higher indexes and
every item that is smaller to lower indexes until the two ranges reach
each other, and then one sort is finished and the two sub-parts are
sorted again iteratively.

In the posted method not the middle VALUE, but the middle INDEX is
fixed (mi, ms). Every time when the two "while" loops are called with
CompareFunc, the parameter is NOT the original value, but the original
index.
If the array "behaves" well the difference cannot be noticed
(typically with low number of data points).
But, if not, when the middle element is swapped with another element,
the reference is changing.

Try as an example {7,6,1,2,3,4,5}.
In the original quicksort the check is against VALUE 2. The first swap
is 7-2, giving {2,6,1,7,3,4,5} and the check continues from 6 and 1
again, against the original value of 2. In gives a second swap
immediately, giving {2,1,6,7,3,4,5}. The process stops here and
continues with the split sets of {2,1} and {6,7,3,4,5}. OK, no
overlap.
In the posted version the first swap is the same: {2,6,1,7,3,4,5} and
the check continues from 6 and 1, but against a value of 7 (new value
in the middle position!). So, the first "while" goes up to 7 and the
second "while" stops immediately at 1, but as the index of 7 (3) is
higher than the index of 1 (2), no swap is done, and the iteration
continues with {2,6,1} and {7,3,4,5}, clearly showing that both 6 and
3,4,5 are in the wrong group. From hereon the sorting is correct (in
this example, for larger sets it could have the same problem again),
giving a final "sorted" set of {1,2,6,3,4,5,7}.

Fixing it is relatively easy, need to add a check that if the swap
involved the middle index, than ms need to be updated too. It can
occur only once (later the indexes have already crossed it), so mi do
not need to be updated.
Code: [Select]      Move(SwapBuf, pb[hs], Stride);
      // begin fix: update ms if the reference point is moved
      if li=mi then ms:=hs;
      if hi=mi then ms:=ls;
      // end fix
      inc(ls, Stride); inc(li);

----------------------------------------------------------------------
valdir.marcos · 2019-12-28 21:51

Very interesting discussion.

Quote from: sam707 on December 14, 2016, 05:09:32 pmQuote from: Jay on
November 28, 2016, 10:28:17 amI know it's easy enough to write your
own from scratchhuh? 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
Quote from: skalogryz on December 14, 2016, 05:17:01 pmYeah, I posted
this old-school approach before.
Well, let me do it again!
Quote from: sam707 on October 02, 2015, 12:12:23 amQuote from:
BeniBela on October 02, 2015, 12:07:28 amQuote from: sam707 on October
02, 2015, 12:01:08 amhey guys, since 1969 Pascal is a "strong typed"
language, ask wikipomidia or whatever, i dont think you are going to
make the team change the compiler for a weak soup like basic or
sumthing... looolooooloooOOOL
https://en.wikipedia.org/wiki/Strong_and_weak_typing
I suggest you either to learn FreeBasic compiler, either to use
variants LOLLet's quote this:
> Java itself may be considered more strongly typed than Pascal
Yet in Java, arrays of the same type are the same type no matter,
which file they are declared in.java is NOT a language its a mix soup
subdialect of c++ with one and only one paradigm = object.. plus it is
even NOT a compiler producing machine native code but PCode wich java
claimed to be new concept but HAHAH new since Fortran 77 (1977 SO! new
my ass)I've use a little and for a very short time Fortran 77 in 1990
and I neither knew nor realized that it used a virtual machine on that
time.

Quote from: sam707 on October 02, 2015, 12:15:33 ammy opinion is
simple = bad workers always complain they have bad tools .. they are
never guilty but the tools are

----------------------------------------------------------------------
avk · 2019-12-29 09:55

@jollytall, you seem to be right. Would you be kind enough to update
the wiki?
But IMO, those who use this sorting, definitely should not complain
that the compiler generates not quite optimal code.

----------------------------------------------------------------------
jollytall · 2019-12-30 08:38

Quote from: avk on December 29, 2019, 10:55:39 am@jollytall, you seem
to be right. Would you be kind enough to update the wiki?

I would be happy, but three issues:
1. I hope the community can validate that my patch is really fixing
the issue in all cases
2. I hope skalogryz will also read it, and build it in his own code,
maybe more elegantly
3. I do not know, how to update the wiki (but probably can find it
somewhere).

----------------------------------------------------------------------
jollytall · 2021-10-15 08:00

It took me some time, but finally I went to the wiki page and in the
Discussion section commented the bug. I did not want to touch the main
page, but probably it also should be done.
I also uploaded the source with some more descriptive name changes
(and in my own style) to Github:
https://github.com/zsoltszakaly/quicksortforpascal

----------------------------------------------------------------------
jollytall · 2021-11-11 07:13

JFYI: I also updated the source code on the Wiki main page:
https://wiki.freepascal.org/Array_sort

----------------------------------------------------------------------
marcov · 2021-11-11 09:16

Thank you!