I can not find logical error in my code - Quick sort

[Milsa]

Application freezes.

Second sorting works (it is in comment - it is slow sorting only for a test).

If I have breakpoint on first QuickSort recursive calling (line 45), watching on variables l, hi, li, h is ok. Apolication shows invalid steps (jump to middle of QuickSort procedure) after breakpoint (push F8) on these values:
l=1
hi=1
lo=1
h=2
I do not understand it.

Application freezes. FSorted is still 0. Lines 46 and more are ignored. 

[avk]

Your quicksort code can be fixed as follows:

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

1. class procedure TGenSort.QuickSort(var a: array of T; l, h: Integer; Cmp: specialize TGenCompare<T>);
2. var
3.   li, hi, mi: Integer;
4.   x: T;
5. begin
6.   li := l;
7.   hi := h;
8.   mi := (li + hi) div 2;
9.   repeat
10.     while Cmp(a[li], a[mi]) < 0 do
11.       li += 1;
12.     while Cmp(a[mi], a[hi]) < 0 do
13.       hi -= 1;
14.     //if li < hi then
15.     if li <= hi then
16.       begin
17.         x := a[li];
18.         a[li] := a[hi];
19.         a[hi] := x;
20.         //////////
21.         if mi = li then
22.           mi := hi
23.         else
24.           if mi = hi then
25.             mi := li;
26.         //////////
27.         li += 1;
28.         hi -= 1;
29.       end;
30.   until li > hi;
31.   if hi > l then
32.     QuickSort(a, l, hi, Cmp);
33.   if li < h then
34.     QuickSort(a, li, h, Cmp);
35. end;  
36.  

But if you take the value of an element as a pivot, the quick sort code will be a little easier:

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

1. class procedure TGenSort.QuickSort(var a: array of T; l, h: Integer; Cmp: specialize TGenCompare<T>);
2. var
3.   li, hi: Integer;
4.   pivot, x: T;
5. begin
6.   li := l;
7.   hi := h;
8.   pivot := a[(li + hi) shr 1];
9.   repeat
10.     while Cmp(a[li], pivot) < 0 do
11.       li += 1;
12.     while Cmp(pivot, a[hi]) < 0 do
13.       hi -= 1;
14.     if li <= hi then
15.       begin
16.         x := a[li];
17.         a[li] := a[hi];
18.         a[hi] := x;
19.         li += 1;
20.         hi -= 1;
21.       end;
22.   until li > hi;
23.   if hi > l then
24.     QuickSort(a, l, hi, Cmp);
25.   if li < h then
26.     QuickSort(a, li, h, Cmp);
27. end;
28.  

But I'm curious why not use a ready-made sort function from some library?

[Milsa]

I wanted some sorting directly from FPC, but Google gave me this:
Google search line: fpc sort
And this is first link:
https://wiki.freepascal.org/Array_sort

[process_1]

Little advice:

For some critical functions/methods/classes in your project, never use built-in solutions. Small regression or a bug and whole application will become useless!

[avk]

I wanted some sorting directly from FPC, but Google gave me this:
Google search line: fpc sort
And this is first link:
https://wiki.freepascal.org/Array_sort

Hmm, it seems this particular implementation contains an error(see this post).

In addition, in its pure form, quicksort has a number of drawbacks, and libraries are trying to eliminate these drawbacks(with more or less success). The built-in quick sort implementation is in the sortbase unit(untyped pointers), generic array sorting can be found in the fcl-stl(unit garrayutils) and rtl-generics(class TArrayHelper) packages. As a third-party library I can offer LGenerics.