Sunday, July 26, 2015

sort items by priority in array inplace

enum priority:
    high = 1,
    medium = 2,
    low = 3

// sort by priority inplace
(a):
    highcount, mediumcount, lowcount = getprioritycounts(a)
    moveitems(a, highcount, mediumcount, lowcount)

getprioritycounts(a):
    for i = 0, i < a.length, i++:
        priority = a[i].priority()
        if priority == priority.high:
            highcount++
        else if priority == priority.medium:
            mediumcount++
        else if priority == priority.low:
            lowcount++
    return highcount, mediumcount, lowcount

moveitems(a, highcount, mediumcount, lowcount):
    highi = 0, mediumi = highcount, lowi = mediumi + mediumcount
    // move the high priority items
    for i = highi, i < highcount,:
        priority = a[i].priority()
        if priority == priority.high:
            i++
        else if priority == priority.medium:
            swap(a, i, mediumi)
            mediumi++
        else if priority == priority.low:
            swap(a, i, lowi)
            lowi++
    // move the medium priority items
    for i = mediumi, i < highcount + mediumcount,:
        priority = a[i].priority()
        if priority == priority.high:
            // this should not occur
            throw
        else if priority == priority.medium:
            i++
        else if priority == priority.low:
            swap(a, i, lowi)
            lowi++

This works for n priorities.
// sort asc by priority inplace asc
// assume priorities is sorted asc too
(a, priorities):
    if a == null || priorities == null:
        throw
    if a.length() == 0 || priorities.length() == 0:
        return
    //priorities.sort()
    start = 0, end = a.length()-1
    for p = 0, p < priorities.length()-1, p++: // skip last
        priority = priorities[p]
        while start < end:
            item = a[start]
            if item.priority() == priority:
                start++
            else:
                swap(a, start, end)
                end--
        end = a.length()-1
[Hat tip to ts]

No comments:

Post a Comment