shell_sort.mdtlbl

# 这是一个使用`Sedgewick`增量的希尔排序(`ShellSort`)
# 并且将增量提前计算为常量来内联, 避免需要一个额外的内存元来存储增量表
# 或者需要每次增量变更进行较为复杂的公式计算

const Memory = bank1;

const Read = (
    take Res = _0;
    take Idx = _1;
    read Res Memory Idx;
    setres Res;
);
const Write = (
    take Num = _0;
    take Idx = _1;
    write Num Memory Idx;
);
const GetGap = (
    take Res = _0;
    take Idx = _1;
    setres Res;
    switch Idx {
        break;
    case: $ = 1;
    case: $ = 5;
    case: $ = 19;
    case: $ = 41;
    case: $ = 109;
    case: $ = 209;
    case: $ = 505;
    case: $ = 929;
    case: $ = 2161;
    case: $ = 3905;
    case: $ = 8929;
    case: $ = 16001;
    case: $ = 36289;
    case: $ = 64769;
    case: $ = 146305;
    case: $ = 260609;
    case: $ = 587521;
    case: $ = 1045505;
    case: $ = 2354689;
    case: $ = 4188161;
    case: $ = 9427969;
    case: $ = 16764929;
    case: $ = 37730305;
    case: $ = 67084289;
    case: $ = 150958081;
    case: $ = 268386305;
    case: $ = 603906049;
    case: $ = 1073643521;
    case: $ = 2415771649;
    case: $ = 4294770689;
    case: $ = 9663381505;
    case: $ = 17179475969;
    }
);
const ShellSort = (
    take Start = _0;
    take Stop = _1;
    const Cmp = _2;

    take Len = ($ = Stop - Start;);
    take GapI = ({}$ = 0;);
    gwhile GetGap[() GapI] < Len { GapI = GapI + 1; }
    while GapI >= 0 {
        take Gap = GetGap[() GapI];
        take GStart = ($ = Start + Gap;);
        take I = ({}$ = GStart;);
        while I < Stop {
            take Num = Read[() I];
            take J = ({}$ = I;) Num1 = ();
            while J >= GStart
            && ({take Read[Num1 ($ = J - Gap;)] _0 = Num _1 = Num1;} => Cmp)
            {
                take Write[Num1 J];
                J = J - Gap;
            }
            take Write[Num J];
            I = I + 1;
        }
        GapI = GapI - 1;
    }
);

const SWITCH = switch1; # 按钮
break (sensor $ SWITCH @enabled;);
take ShellSort[0 (read $ cell1 0;) goto(_0 < _1)];
control enabled SWITCH true 0 0 0;