### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: I can not find logical error in my code - Quick sort  (Read 683 times)

#### Milsa

• Full Member
• Posts: 213
##### I can not find logical error in my code - Quick sort
« on: June 28, 2020, 08:42:21 pm »
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.
I work with Lazarus 2.0.10, FPC 3.2.0, SVN 63526
This information is actual to: 1st Aug 2020

#### avk

• Sr. Member
• Posts: 303
##### Re: I can not find logical error in my code - Quick sort
« Reply #1 on: June 29, 2020, 04:21:41 pm »
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

• Full Member
• Posts: 213
##### Re: I can not find logical error in my code - Quick sort
« Reply #2 on: June 29, 2020, 11:09:56 pm »
I wanted some sorting directly from FPC, but Google gave me this:
https://wiki.freepascal.org/Array_sort
I work with Lazarus 2.0.10, FPC 3.2.0, SVN 63526
This information is actual to: 1st Aug 2020

#### process_1

• Guest
##### Re: I can not find logical error in my code - Quick sort
« Reply #3 on: June 30, 2020, 05:27:14 am »

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

• Sr. Member
• Posts: 303
##### Re: I can not find logical error in my code - Quick sort
« Reply #4 on: June 30, 2020, 07:26:03 am »
I wanted some sorting directly from FPC, but Google gave me this: