Forum > LCL
LCLProc MergeSort seems not stable
apeoperaio:
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 [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} --- procedure SmallSort(StartPos, EndPos: PtrInt); // use insertion sort for small lists var i: PtrInt; Best: PtrInt; j: PtrInt; Item: Pointer; begin for i:=StartPos to EndPos-1 do begin Best:=i; for j:=i+1 to EndPos do if OnCompare(List[Best],List[j])>0 then Best:=j; if Best>i then begin Item:=List[i]; List[i]:=List[Best]; List[Best]:=Item; end; end; end;
Would be the following implementation stable?
--- Code: Pascal [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} --- procedure SmallSort(StartPos, EndPos: PtrInt); // use insertion sort for small lists var i: PtrInt; Best: PtrInt; j: PtrInt; Item: Pointer; begin for i:=StartPos to EndPos-1 do begin Best:=i; for j:=i+1 to EndPos do if OnCompare(List[Best],List[j])>0 then Best:=j; if Best>i then begin Item:=List[Best]; List.Delete(Best); List.Insert(i, Item); end; end; end;
Thaddy:
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 [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---program SortOfAnIssue;{$mode objfpc}{$H+}uses types; procedure MergeSort(var A: TIntegerDynArray; const Buf: TIntegerDynArray; const Left, Right: Integer);inline;overload;var Center, I, J, K: Integer;begin if Right - Left > 1 then begin Center := (Left + Right) div 2; MergeSort(A, Buf, Left, Center); MergeSort(A, Buf, Center, Right); for I := Left to Center - 1 do Buf[I] := A[I]; I := Left; J := Center; K := Left; while I < Center do begin if J >= Right then A[K] := Buf[I] else if Buf[I] < A[J] then A[K] := Buf[I] else A[K] := A[J]; Inc(I); Inc(K); if J < Right then Inc(J); end; end else if Right - Left = 1 then // adjust here, can be anything small that suits you. begin // Insertion Sort for small sizes J := Left; while (J > 0) and (A[J-1] > A[J]) do begin I := A[J-1]; A[J-1] := A[J]; A[J] := I; Dec(J); end; end;end; procedure MergeSort(var A: TIntegerDynArray);inline;overload;begin MergeSort(A, A, 0, Length(A));end; var Items:TIntegerDynArray = { objfpc } (707,707,101); // mode delphi is: [707,707,101]; // square brackets i:integer;begin mergesort(Items); for i in items do writeln(i);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.
apeoperaio:
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:
Devil is in details. It depends what algorithm does with the same values.
--- Code: Pascal [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} --- if OnCompare(List[Best],List[j])>0 thenI.e. change from ">" to " >=" can make it stable.
But of course, it depends how is "OnCompare" implemented.
Thaddy:
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.
Navigation
[0] Message Index
[#] Next page