CODEWITHSUNDEEP
pythonalgorithmsortingpython-3.xinsertion-sort
eddiewastaken
eddiewastaken

Reputation: 832

How do I insertion sort a list of lists?

def insertionSort(mylist):
for index in range(1, len(mylist)):
    currentvalue = mylist[index]
    position = index
    while position > 0 and mylist[position - 1] > currentvalue:
        mylist[position] = mylist[position - 1]
        position = position - 1
    mylist[position] = currentvalue
return mylist

Above I have some code which can insertion sort a list of lists, for example

list1 = [(12,45,62),(78,35,72),(34,52,75)]
insertionSort(list1)

yields

list1 = [(12,45,62),(34,52,75),(78,35,72)]

Which sorts each sub-list by the first element (12, 34 and 78). How can I make the insertion sort sort by the second and third elements of the sub-lists?

Upvotes: 2

Views: 1927

Answers (1)

tobias_k
tobias_k

Reputation: 82899

Sorting functions in the Python library provide a key parameter for this purpose, determining the function used to get the key for comparing two elements. You can do the same for your own insertion sort. The default value for this parameter could be a function returning the element itself, but it can be overridden with any other key function.

def insertionSort(mylist, key=lambda x: x):
    for index in range(1, len(mylist)):
        currentvalue = mylist[index]
        position = index
        while position > 0 and key(mylist[position - 1]) > key(currentvalue):
            mylist[position] = mylist[position - 1]
            position = position - 1
        mylist[position] = currentvalue
    return mylist

Examples:

>>> list1 = [(12,45,62),(78,35,72),(34,52,75)]
>>> insertionSort(list1)
[(12, 45, 62), (34, 52, 75), (78, 35, 72)]
>>> insertionSort(list1, key=lambda x: x[1])
[(78, 35, 72), (12, 45, 62), (34, 52, 75)]

Note: In sort and sorted, the key function will be evaluated only once for each value in the list, whereas in this version, it is evaluated for every comparison. If you want to call the function just once, you could, e.g., cache the key values in a dictionary.

Upvotes: 3

Related Questions