Maintaining a sorted array of tuples ~ Python

Hello Pythonistas!

After some Christmas despair and endless reference searching  I thought I could do a good thing and put everything together here ;)

Objective : Maintain a sorted array of tuples in Python

For our recipe you will need : 1 array of tuples, 1 array of comparable values , this post

        The main array (from now on "tupArray") is an array of tuples (say tuples of three values) so we have tupArray = [(0,0,0)]  keep in mind the value we want to use to keep the array sorted HAS to be comparable. The second array (from now on "indexArray") is going to act as an index for the first so it will be sorted too and it will contain the element from each tuple that is our sorting index. Confused? Let me clear it out a bit with an example. Say we want to sort our array of tuples based on the second value of each tuple. This would be tupArray[i][1].  Then given an already populated and sorted tupArray, the indexArray would be created like this:

for elem in tupArray:
     indexArray.append (elem[1])

        That's it. We now have both tupArray and indexArray populated and sorted. Now to maintaining. This was probably the hardest part, not to understand but to find information about. First make sure you're familiar with slicing, you can tag along in any case but having a basic understanding of slicing would help you understand much faster.
        We will be utilizing a function called bisect. What bisect does is it returns the position in which you would insert an element in a sorted array in order for it to remain sorted. Bisect has a few variants, that allow you to define whether you want the new element to be placed before or after any existing elements with the same value (bisect_left is for before and bisect_right is for after we will be using the later). First import bisect:

import bisect

Then we call bisect giving indexArray and the element to be inserted as values:

insertIndex =  bisect.bisect_right (indexArray, elementToInsert)

Then we place it in indexArray using slicing:

indexArray[insertIndex:insertIndex] = elementToInsert

This will create a NEW element at indexArray[insertIndex] and not replace the one already there (like indexArray[insertIndex] = elementToInsert would). Finally, we have to insert our tuple to tupArray. For that we'll be using slicing again:

tupArray[insertIndex:insertIndex] = tupleToInsert

And that's really all there is to it! We've made an index list out of our array of tuples and managed to insert a new element without having to resort the array. A little heads up, if you are to pop or in any way remove elements from tupArray (and you most probably are) REMEMBER to do the exact same operation to indexArray too!

Until next time, have fun and happy coding!