What is a typical way to add an inverse function to an insertion sort?

Question

I wrote the following insertion sorting algorithm

def insertionSort(L, reverse=False): for j in xrange(1,len(L)): valToInsert = L[j] i=j-1 while i>=0 and L[i] > valToInsert: L[i+1] = L[i] i-=1 L[i+1] = valToInsert return L 

Edit: all you have to do is change the final> to <to make it work the other way around.

However, what do most people do in these situations? Write the algorithm twice in two if statements, where is it> and the other is where is it <instead of? What is the “right” way to typically manage such scenarios when the change is minor, but it just changes the nature of the loop / code as a whole?

I know this question is a bit subjective.

Answer 1

You can use a variable for a smaller operator:

 import operator def insertionSort(L, reverse=False): lt = operator.gt if reverse else operator.lt for j in xrange(1,len(L)): valToInsert = L[j] i = j-1 while 0 <= i and lt(valToInsert, L[i]): L[i+1] = L[i] i -= 1 L[i+1] = valToInsert return L 

Answer 2

Option 1:

 def insertionSort(L, reverse=False): # loop is the same... if reverse: L.reverse() return L 

Option 2:

 def insertionSort(L, reverse=False): if reverse: cmpfunc = lambda a, b: cmp(b, a) else: cmpfunc = cmp for j in xrange(1,len(L)): valToInsert = L[j] i=j-1 while i>=0 and cmpfunc(L[i], valToInsert) > 0: L[i+1] = L[i] i-=1 L[i+1] = valToInsert return L 

Answer 3

You will probably notice that sorted and list.sort and all other functions that perform any potentially-decorated processing have a key parameter, and those that specifically order also have a reverse parameter. (The Mini-HOWTO sorting describes this.)

So, you can see how they are implemented. Unfortunately, in CPython all this stuff is implemented in C. Plus, it uses its own algorithm called "timsort" (described in listsort.txt ). But I think that here you can explain the key parts, as it is dazzlingly simple. The list.sort code list.sort separate from the sorted code, and they are both distributed across many functions. But if you just look at the top-level listsort , you will see how it handles the reverse flag:

 1982 /* Reverse sort stability achieved by initially reversing the list, 1983 applying a stable forward sort, then reversing the final result. */ 1984 if (reverse) { 1985 if (keys != NULL) 1986 reverse_slice(&keys[0], &keys[saved_ob_size]); 1987 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]); 1988 } 

Why change the list at the beginning and at the end? Well, in the case where the list is primarily sorted, many sorting algorithms, including both timsort and your insert assortment, will be much better to start in the correct order than in the reverse order. Yes, it sends an O (N) reverse call, but you already do one of them - and since any sorting algorithm has at least O (N log N), and yours is O (N ^ 2), this does not make it algorithmically worse. Of course, for a small N and a better grade and list in random order, this wasted 2N is pretty close to N log N, so this can make a difference in practice. It will be a difference that disappears as N gets huge, but if you sort millions of small list s, rather than a few huge ones, it can be interesting to worry about.

Secondly, notice that it does the opposite, creating a reverse slice. This, at least, could possibly be optimized by referring to the original list object with __getitem__ in reverse order, that is, two U-turns are actually O (1). The easiest way to do this is to literally create a backslash: lst[::-1] . Unfortunately, this actually creates a new backward list , so timsort includes its own backslash object. But you can do the same in Python by creating a ReversedList class.

It probably won't be that fast in CPython, because the cost of extra function calls is probably high enough to drown out the differences. But you complain about the algorithmic cost of two reverse calls, and this solves the problem, effectively the same way as the built-in sorting functions.

You can also see how PyPy does it. Its list is implemented in listobject.py . He delegates one of several strategy classes depending on what the list contains, but if you look at all the strategies (except those that have nothing in common), they basically do the same thing: sort list, then reverse it.

So, this is good enough for CPython, and for PyPy ... this is probably enough for you.