Recent

Author Topic: I can not find logical error in my code - Quick sort  (Read 627 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.  :o
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: 273
    • my self-education project
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:
Google search line: fpc sort
And this is first link:
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

  • Full Member
  • ***
  • Posts: 118
Re: I can not find logical error in my code - Quick sort
« Reply #3 on: June 30, 2020, 05:27:14 am »
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!
FPC 3.2.0, Lazarus 2.0.10, KDE Neon 64-bit

avk

  • Sr. Member
  • ****
  • Posts: 273
    • my self-education project
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:
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. :)

 

TinyPortal © 2005-2018