Recent

Author Topic: LCLProc MergeSort seems not stable  (Read 1726 times)

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
LCLProc MergeSort seems not stable
« on: January 30, 2023, 09:58:54 am »
I was looking for a stable sorting algorithm and I came up to the MergeSort algotithm implemented in LCLProc.
Wikipedia states that most implementations of merge sort produce a stable sort.
Anyway the MergeSort implementation seems not stable.
Let's suppose we  have a list of three items:
'707' (idx 0)
'707' (idx 1)
'101' (idx 2)

Looking at the MergeSort implementation the final results will be:
'101' (idx 2)
'707' (idx 1)
'707' (idx 0)

That's not stable.

The original implementation is:

Code: Pascal  [Select][+][-]
  1.   procedure SmallSort(StartPos, EndPos: PtrInt);
  2.   // use insertion sort for small lists
  3.   var
  4.     i: PtrInt;
  5.     Best: PtrInt;
  6.     j: PtrInt;
  7.     Item: Pointer;
  8.   begin
  9.     for i:=StartPos to EndPos-1 do begin
  10.       Best:=i;
  11.       for j:=i+1 to EndPos do
  12.         if OnCompare(List[Best],List[j])>0 then
  13.           Best:=j;
  14.       if Best>i then begin
  15.         Item:=List[i];
  16.         List[i]:=List[Best];
  17.         List[Best]:=Item;
  18.       end;
  19.     end;
  20.   end;
  21.  

Would be the following implementation stable?

Code: Pascal  [Select][+][-]
  1.   procedure SmallSort(StartPos, EndPos: PtrInt);
  2.   // use insertion sort for small lists
  3.   var
  4.     i: PtrInt;
  5.     Best: PtrInt;
  6.     j: PtrInt;
  7.     Item: Pointer;
  8.   begin
  9.     for i:=StartPos to EndPos-1 do begin
  10.       Best:=i;
  11.       for j:=i+1 to EndPos do
  12.         if OnCompare(List[Best],List[j])>0 then
  13.           Best:=j;
  14.       if Best>i then begin
  15.         Item:=List[Best];
  16.         List.Delete(Best);
  17.         List.Insert(i, Item);
  18.       end;
  19.     end;
  20.   end;
  21.  


Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: LCLProc MergeSort seems not stable
« Reply #1 on: January 30, 2023, 11:23:35 am »
Compare with the two Rosetta code entries?
rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Pascal

Note that with both examples and the size of your array, you are not testing mergesort, but insertion sort.
Anyway, I found it fun, so I wrote a version from scratch that can be proven stable:
Code: Pascal  [Select][+][-]
  1. program SortOfAnIssue;
  2. {$mode objfpc}{$H+}
  3. uses types;
  4.  
  5. procedure MergeSort(var A: TIntegerDynArray; const Buf: TIntegerDynArray; const Left, Right: Integer);inline;overload;
  6. var
  7.   Center, I, J, K: Integer;
  8. begin
  9.   if Right - Left > 1 then
  10.   begin
  11.     Center := (Left + Right) div 2;
  12.     MergeSort(A, Buf, Left, Center);
  13.     MergeSort(A, Buf, Center, Right);
  14.     for I := Left to Center - 1 do
  15.       Buf[I] := A[I];
  16.     I := Left;
  17.     J := Center;
  18.     K := Left;
  19.     while I < Center  do
  20.     begin
  21.       if J >= Right then
  22.         A[K] := Buf[I]
  23.       else if Buf[I] < A[J] then
  24.         A[K] := Buf[I]
  25.       else
  26.         A[K] := A[J];
  27.       Inc(I);
  28.       Inc(K);
  29.       if J < Right then
  30.         Inc(J);
  31.     end;
  32.   end
  33.   else if Right - Left = 1 then  // adjust here, can be anything small that suits you.
  34.   begin
  35.     // Insertion Sort for small sizes
  36.     J := Left;
  37.     while (J > 0) and (A[J-1] > A[J]) do
  38.     begin
  39.       I := A[J-1];
  40.       A[J-1] := A[J];
  41.       A[J] := I;
  42.       Dec(J);
  43.     end;
  44.   end;
  45. end;
  46.  
  47. procedure MergeSort(var A: TIntegerDynArray);inline;overload;
  48. begin
  49.   MergeSort(A, A, 0, Length(A));
  50. end;
  51.  
  52. var
  53.  Items:TIntegerDynArray = { objfpc } (707,707,101);  // mode delphi is: [707,707,101]; // square brackets
  54.  i:integer;
  55. begin
  56.   mergesort(Items);
  57.   for i in items do writeln(i);
  58. end.
That is, keeping the rosetta code entries in mind and hopefully some prior knowledge left-overs.
There is still room for improvement: fast fingers, slow mind.
May also be slow speed, but point was to prove stability.
« Last Edit: January 30, 2023, 12:15:24 pm by Thaddy »
Specialize a type, not a var.

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: LCLProc MergeSort seems not stable
« Reply #2 on: January 30, 2023, 03:23:00 pm »
Thank you. I will look at the code.
Anyway, my list has more than 3 items. It was just an example to show that the SmallSort procedure inside the LCLProc mergesort seems to break the stability.

Blaazen

  • Hero Member
  • *****
  • Posts: 3237
  • POKE 54296,15
    • Eye-Candy Controls
Re: LCLProc MergeSort seems not stable
« Reply #3 on: January 30, 2023, 04:59:01 pm »
Devil is in details. It depends what algorithm does with the same values.
Code: Pascal  [Select][+][-]
  1.  if OnCompare(List[Best],List[j])>0 then
I.e. change from ">" to "  >=" can make it stable.

But of course, it depends how is "OnCompare" implemented.
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: LCLProc MergeSort seems not stable
« Reply #4 on: January 30, 2023, 05:30:39 pm »
Indeed, if lcl implements right to left evaluation that is is the cause.
(But my code shows the two conditions to be met for a stable sort even if mixing insertion and Merge, which is technically a hybrid)

Anyway: the lcl implementation looks broken.
Specialize a type, not a var.

Blaazen

  • Hero Member
  • *****
  • Posts: 3237
  • POKE 54296,15
    • Eye-Candy Controls
Re: LCLProc MergeSort seems not stable
« Reply #5 on: January 30, 2023, 05:33:31 pm »
Guys, you mystified me!  ;D

It's not InsertionSort, it is SelectionSort. SelectionSort - by wiki - can be implemented as a stable but usually is not.

https://en.wikipedia.org/wiki/Selection_sort

BTW: Why the link replaces h t t p with ** ?
« Last Edit: January 30, 2023, 05:40:29 pm by Blaazen »
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

Fred vS

  • Hero Member
  • *****
  • Posts: 3158
    • StrumPract is the musicians best friend
I use Lazarus 2.2.0 32/64 and FPC 3.2.2 32/64 on Debian 11 64 bit, Windows 10, Windows 7 32/64, Windows XP 32,  FreeBSD 64.
Widgetset: fpGUI, MSEgui, Win32, GTK2, Qt.

https://github.com/fredvs
https://gitlab.com/fredvs
https://codeberg.org/fredvs

Blaazen

  • Hero Member
  • *****
  • Posts: 3237
  • POKE 54296,15
    • Eye-Candy Controls
Re: LCLProc MergeSort seems not stable
« Reply #7 on: January 30, 2023, 08:35:19 pm »
To make the original Selection Sort stable is needed to replace:
Code: Pascal  [Select][+][-]
  1.  if Best>i then begin
  2.         Item:=List[i];
  3.         List[i]:=List[Best];
  4.         List[Best]:=Item;
  5.       end;

with
Code: Pascal  [Select][+][-]
  1.   if Best>i then begin
  2.         Item:=List[Best];
  3.         system.Move(List[i], List[i+1], (Best-i)*sizeOf(Item));
  4.         List[i]:=Item;
  5.       end;
i.e. shift all items instead of just swap two. Of course, List must be continuous memory (array).
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: LCLProc MergeSort seems not stable
« Reply #8 on: February 08, 2023, 12:26:02 pm »
@Blaaze, I tried your code but if I use it I got the error:
lclproc.pas(1150,39) Error: Can't take the address of constant expressions

on:
Code: Pascal  [Select][+][-]
  1. system.Move(List[i], List[i+1], (Best-i)*sizeOf(Item));

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: LCLProc MergeSort seems not stable
« Reply #9 on: February 08, 2023, 01:52:45 pm »
That's why I wrote a stable sort for both cases. See above.
Specialize a type, not a var.

Blaazen

  • Hero Member
  • *****
  • Posts: 3237
  • POKE 54296,15
    • Eye-Candy Controls
Re: LCLProc MergeSort seems not stable
« Reply #10 on: February 08, 2023, 05:10:19 pm »
system.Move can't work here. List is TStrings where you access items via abstract getters and setters. i.e. it's not continuous memory.
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: LCLProc MergeSort seems not stable
« Reply #11 on: February 13, 2023, 09:30:47 am »
That's why I wrote a stable sort for both cases. See above.

Thanks!

 

TinyPortal © 2005-2018