How to do stable in-place relative reordering of elements in a list

Question

I have this function:

def relative_reorder(my_list, before, after):
    backup_of_my_list = list(my_list)
    def my_key(item):
        if item is after:
            return backup_of_my_list.index(before) * 2 + 1
        else:
            return backup_of_my_list.index(item) * 2
    my_list.sort(key=my_key)

That can be used like this:

stack = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9]
relative_reorder(stack, 9, 7)
print(stack)
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 9, 9, 8, 8]

But I would like like to improve sorting stability

I would consider outputs such as these preferable:

[1, 2, 3, 4, 5, 6, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 7 ,7]
[1, 2, 3, 4, 5, 6, 9, 9, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8]

The goal is to reorder the list so that all occurrences of 9 are of a lower index than all occurrences of 7, while maintaining as much stability in the list as possible. One use of this is might be to order some tasks that might need to run, and we know that a certain task should always run before another task...

Those results don't seem consistent... What exactly are you trying to do... The first looks like you're just moving a certain value to the end... I'm not sure what ordering is actually occurring here... — Jon Clements, Jan 17 '14 at 11:02
@JonClements I have modified the question, hopefully my goal is clearer now — Dave Butler, Jan 17 '14 at 16:35

score 0 · Accepted Answer · answered Jan 23 '14 at 04:15

def last_index(l, value):
    """
    Find the last occurance of value in the list
    """
    # http://stackoverflow.com/q/522372/693869#comment336488_522401
    return len(l) - 1 - l[::-1].index(value)

def move_item(l, old, new):
    """
    Move an item from an old index to a new index
    """
    l.insert(new, l.pop(old))

def relative_reorder(l, before, after):
    """
    reorder list so that all occurrences of before are of a lower 
    index than all occurrences of after
    """
    while last_index(l, before) > l.index(after):
        move_item(l, last_index(l, before), l.index(after))

stack = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9]
relative_reorder(stack, 9, 7)
print(stack)
[1, 2, 3, 4, 5, 6, 9, 9, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8]

If anyone has a cleaner version, ill accept it

How to do stable in-place relative reordering of elements in a list

1 Answers1