5 
ss = [(0,'bb','jj'), (1,'aa','mm'), (2,'aa','kk'),(3,'bb','ee'),(4,'gg','ff')]

for x in ss:
    pp = <somthing>

Using Python, is it possible to insert from ss into pp and maintain pp sorted by two attributes, let's say by the 2nd then 3rd position in order to have the following result (both attributes ascending):

pp = [(2, 'aa', 'kk'), (1, 'aa', 'mm'), (3, 'bb', 'ee'), (0, 'bb', 'jj'), (4, 'gg', 'ff')]

Or (both attributes descending):

pp = [(4, 'gg', 'ff'), (0, 'bb', 'jj'), (3, 'bb', 'ee'), (1, 'aa', 'mm'), (2, 'aa', 'kk')]

I don't want to use the following two statments after the loop which already do the job:

pp = sorted(ss, key = operator.itemgetter(1, 2))
pp = sorted(ss, key = operator.itemgetter(1, 2), reverse=True)

Because i am dealing with a very long list and i already have the loop which i want to reuse for sorting as well.

Improve this question
4
  • Take a look at the bisect module.
    – poke
    Commented Jan 24, 2014 at 14:38
  • 1
    Append the new elements to pp in your loop (or just write pp.extend(ss)), then call pp.sort with the same arguments as the calls to sorted that you don't want to do. Thank to Timsort, this is the efficient way to maintain a sorted list in Python.
    – Steve Jessop
    Commented Jan 24, 2014 at 15:28
  • Hmm, just realised that you don't keep the original contents of pp. Then ignore the part about extend. I don't understand why you wouldn't want to use the sorted lines. Regardless of the size of the list, sorted is an efficient way to create a sorted copy of it. You will not get better performance by repeatedly inserting each element into its correct place. That's called "insertion sort", and if it was a good sorting algorithm then sorted would probably use it. For large lists it isn't good.
    – Steve Jessop
    Commented Jan 24, 2014 at 15:34
  • I would use a priority queue implemented with heapq module functions. But it would require extra work because your sort criterion ain't trivial. Take a look at this: docs.python.org/2/library/…
    – Paulo Bu
    Commented Jan 24, 2014 at 15:41

1 Answer 1

Reset to default
2

You can use binary search during every insertion.

ss = [(0,'bb','jj'), (1,'aa','mm'), (2,'aa','kk'),(3,'bb','ee'),(4,'gg','ff')]

l = []

def insert_sort(l, e, compare):
    lo = 0
    hi = len(l)
    while lo < hi:
        mid = (lo+hi) / 2
        if compare(e, l[mid]):
            lo = mid + 1
        else: 
            hi = mid
    l.insert(lo, e)

ascend_list = []
descend_list = []

for i in ss:
    insert_sort(ascend_list, i, lambda x, y: x[1:] >= y[1:])

for i in ss:
    insert_sort(descend_list, i, lambda x, y: x[1:] < y[1:])

print ascend_list
print descend_list
Improve this answer
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.