Forum > LCL
LCLProc MergeSort seems not stable
Blaazen:
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 ** ?
Fred vS:
--- Quote from: Blaazen on January 30, 2023, 05:33:31 pm ---BTW: Why the link replaces h t t p with ** ?
--- End quote ---
https://forum.lazarus.freepascal.org/index.php/topic,62074.0.html
Blaazen:
To make the original Selection Sort stable is needed to replace:
--- 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 Best>i then begin Item:=List[i]; List[i]:=List[Best]; List[Best]:=Item; end;
with
--- 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 Best>i then begin Item:=List[Best]; system.Move(List[i], List[i+1], (Best-i)*sizeOf(Item)); List[i]:=Item; end;i.e. shift all items instead of just swap two. Of course, List must be continuous memory (array).
apeoperaio:
@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 [+][-]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";}};} ---system.Move(List[i], List[i+1], (Best-i)*sizeOf(Item));
Thaddy:
That's why I wrote a stable sort for both cases. See above.
Navigation
[0] Message Index
[#] Next page
[*] Previous page