Moving certain items in a list to the end

Question

I am learning Python and would like to know if there's a better way to rewrite it.

What I am trying to do is to match list A that is passed to a method against a predefined list B. If an item in list A contains an item in list B, I'd like to move it to the end of list A.

# example 1
a = [1, 2, 3, 4, 5]
sanitized_list = sanitize(a) # [3, 4, 5, 1, 2]

# example 2
a = [3, 6, 1, 7, 4]
sanitized_list = sanitize(a) # [3, 6, 7, 4, 1]


def sanitize(arg):
    # predefined list
    predefined_list = [1, 2]

    for item in predefined_list:
        try:
            # check to see if 'arg' contain any item
            # in the predefined list
            i = arg.index(item)

            # save the value of arg[i]
            j = arg[i]

            # remove "j" from "arg"
            arg.pop(i)

            # append item to end of "arg"
            arg.append(j)
        except ValueError:
            pass

    return arg

Answer 1

Notice that what you are trying to do is a reordering of your list to put the elements of predefined_list at the end. Hence your function can be as simple as:

   def sanitize(arg):
      predefined_list = [1, 2]
      # Note that False<True and sort algorithm is stable, so:
      return sorted(arg, key=lambda x: x in predefined_list) 

As an alternative to the lambda, you can use predefined_list.__contains__.

In fact the sorting key is False for elements which are not in predefined_list and True for elements which are contained. Since False<True the latter elements will be moved at the end of the list.

For this to work it is important to know that (at least from Python 2.2) the sort algorithm is guaranteed to be stable, i.e., it does not change the order of elements with the same key.

---

If you want to implement the algorithm yourself I would suggest, as @janos already did, to iterate first on the array to be sorted. This is better for performance and solves the issue of repeated elements.

A possible implementation could be:

def sanitize(arg):
    predefined_list = [1,2]
    pop_count = 0
    for i in range(len(arg)):
       if arg[i-pop_count] in predefined_list:
           arg.append(arg.pop(i-pop_count))
           pop_count += 1

---

About your code: I don't like the use of Exceptions to handle non exceptional situations... however the index method seems to force you to use exceptions so I see no alternative. Anyway I would keep the code inside the try...except block to the minimum, because otherwise you run the risk to hide exceptions caused by some other issue.

Another point is the fact that your algorithm does not handle repeated elements in the original list. You could handle them easily, see below.

Here is a possible cleaning of your implementation:

def sanitize(lst,predefined):
    """
    reorder elements of @lst by moving the elements which also 
    belong to @predefined at the end of the list
    """ 
    for item in predefined:
        while True:
            try:
                i = lst.index(item)
            except ValueError:
                # lst does not contain any occurence of item
                break    
            # move the i-th element to the end of the list
            lst.append(lst.pop(i))

    return lst

Only now I notice that the choice of the algorithm changes the resulting list. In fact you have to decide wether the elements moved at the end must keep the original order in the list (as in my suggested implementations) or must keep the order in the list of items to be removed (as in yours).

Answer 2

For each item in the sanitized list, you do a search in arg. In the worst case scenario arg doesn't contain any of the sanitized elements, so Python has to iterate over the entire list multiple times, each time raising a ValueError.

If you expect arg to have more elements than in the sanitized list in general, then it would be better to reverse the iteration logic. Instead of iterating over sanitized list and checking items in arg, do it the other way around: iterate over arg, checking items in sanitized list. This will be especially good if you make sanitized a set, as in that case checking if an item exists will be very fast, without having to iterate over the entire collection as when using lists.

For example:

def sanitize(arg):
    predefined_list = {1, 2}
    to_move_to_end = []

    for item in arg:
        if item in predefined_list:
            to_move_to_end.append(item)

    for item in to_move_to_end:
        arg.remove(item)

    arg.extend(to_move_to_end)

    return arg

As an added bonus, this handles duplicated items in arg, for example:

# example 3
a = [3, 6, 1, 1, 7, 4]  # gives: [3, 6, 7, 4, 1, 1]

However, as @emanuele-paolini pointed out in his comment:

the second iteration used to move elements has quadratic complexity in the case when most of the elements must be removed. In fact arg.remove itself is linear

To work around that, and if you don't mind duplicating the original array, this would be more efficient:

def sanitize(arg):
    predefined_list = {1, 2}
    sanitized_list = []
    to_move_to_end = []

    for item in arg:
        if item in predefined_list:
            to_move_to_end.append(item)
        else:
            sanitized_list.append(item)

    sanitized_list.extend(to_move_to_end)

    return sanitized_list

Another advantage of this solution is that we don't mutate the function parameter arg (it's a bad practice to reuse function parameters).