isNearlySorted.cfm

<cfscript>
testsAny = [
    // sorted
     [true,[1,2,3,4,5]]
    ,[true,[2,4,6,8,10]]
    
    // 1 swap
    ,[true,[1,2,3,5,4]]
    ,[true,[5,2,3,4,1]]
    ,[true,[1,2,3,5,3]]
    
    // +1 swap
    ,[false,[5,2,3,1,4]]
    ,[false,[2,3,1,5,4]]
    ,[false,[5,1,2,3,4]]
    ,[false,[2,3,1,5,4]]
    ,[false,[2,3,1,4,5]]
    ,[false,[1,2,3,5,2]]
];

testsAdj = [
    // sorted
     [true,[1,2,3,4,5]]
    ,[true,[2,4,6,8,10]]
    
    // 1 swap
    ,[true,[2,1,3,4,5]]
    ,[true,[1,3,2,4,5]]
    ,[true,[1,2,3,5,4]]
    ,[true,[1,2,3,5,3]]
    
    // +1 swap
    ,[false,[5,2,3,4,1]]
    ,[false,[5,2,3,1,4]]
    ,[false,[2,3,1,5,4]]
    ,[false,[5,1,2,3,4]]
    ,[false,[2,3,1,5,4]]
    ,[false,[2,3,1,4,5]]
    ,[false,[1,2,3,5,2]]
];


function isNearlySortedAnywhere(state, current, idx, all) {
    if (isNull(state)) {
        state = {
            swp: {
                 idx:-1
                ,val:-1
                ,cmp:false
            }
            ,len: all.len()
        };
    }
    
    // already reduced to boolean (or numeric for debugging purposes...)
    if (!isStruct(state)) return state;
    
    // check numbers 1 to n-1
    if (idx < state.len) {
        // current should come somewhere later
        if (current > all[idx+1]) {
            // if first encounter mark last sorted value/position
            if (state.swp.val == -1) {
                state.swp.idx = idx;
                state.swp.val = current;
            
            // try to complete a marked swap
            } else if (
                !state.swp.cmp
                // current fits before marked's successor
                && (all[idx+1] <= all[state.swp.idx+1])
                // current fits after marked's predecessor, or marked is first
                && (state.swp.idx == 1 || state.swp.val <= current)
                // marked fits after current's predecessor
                && (state.swp.val >= current)
                // marked can fit in after current either at end of array or before currentpos+2
                && ((idx+1 == state.len) || state.swp.val <= all[idx+2])
            ) {
                state.swp.cmp=true;
                
            // already have a completed swap, or the current swap cannot be completed here
            } else {
                return false;
            }
        }
    
    // current is last
    } else {
    
        // final checks
        return (
            // is sorted
            state.swp.val == -1 
            // marked found valid swap
            || state.swp.cmp
            // can marked be swapped with last and be valid?
            || (
                // marked is greater than current's predecessor
                state.swp.val >= all[idx-1]
                // current is greater than marked's predecessor
                && (state.swp.idx == 1 || current >= all[state.swp.idx-1])
                // current is lte than marked's successor
                && current <= all[state.swp.idx+1]
            )
        );
    }
    
    return state;
}

function isNearlySortedAdjacent(state, current, idx, all) {
    if (isNull(state)) {
        state = {
             foundSwap: false
            ,len: all.len()
        };
    }
    
    // already reduced to boolean (or numeric for debugging purposes...)
    if (!isStruct(state)) return state;
    
    // check numbers 1 to n-1
    if (idx < state.len) {
        // current should come somewhere later
        if (current > all[idx+1]) {
            // if current is also greater than two positions - the swap wont result sorted
            if (
                // not found a swap yet
                !state.foundSwap &&
                (
                // first pair
                   (idx == 1 && state.len > 2 && (current <= all[idx+2]))
                // in range pair
                || (idx > 1 && idx+1 < state.len && (current <= all[idx+2] && all[idx+1] >= all[idx-1]))
                // last pair
                || (idx+1 == state.len && state.len > 2 && (all[idx+1] >= all[idx-1]))
                )
            ) {
                state.foundSwap = true;
            } else {
                return false;
            }
        }
    
    // current is last
    } else {
        return true;
    }
    
    return state;
}

function test(tests, algo) {
    tests.each(function(test) {
        var expect = !!test[1];
        var actual = !!test[2].reduce(algo);
        
        writeoutput(serializeJson(test[2]) & " (nearly) sorted? " & actual & ". Expected " & expect & ".  "&(expect == actual ? "PASS" : "FAIL")&"<br />");
    });
}

writeoutput("tests - any swap<br />");
test(testsAny, isNearlySortedAnywhere);

writeoutput("<hr />");
    
writeoutput("tests - adjacent-only swaps<br />");
test(testsAdj, isNearlySortedAdjacent);

</cfscript>