insertion sort get indices?

I use the following algorithm for insertion sort:

def insertionSort(A):
    indices = [z for z in xrange(len(A))]
    for j in range(1, len(A)):
        key = A[j]
        i = j-1
        while (i>=0) and (A[i]<key):
            A[i+1] = A[i]  
            indices[j-i-1] = i+1         
            i = i-1

        A[i+1] = key

However, I need to maintain a list to map the indices of the original values of A to the sorted values of A, which means if I have a list of [1,3,4,2] after sorting the list = [4,3,2,1] i will have a indices list of [3,1,0,2].

Any pointers? I'm kinda stuck.

EDITED: 开发者_高级运维apologies, sorting in descending order..

Why are you writing a sort? Use Python's builtin sorting.

def sort_with_indexes(data):
    sorted_data = sorted(enumerate(data), key=lambda key: key[1])
    indexes = range(len(data))
    indexes.sort(key=lambda key: sorted_data[key][0])
    return [i[1] for i in sorted_data], indexes

data, indexes = sort_with_indexes([1,3,4,2])
print data, indexes

the fix to NullUserException's answer is simple:

sorted_list, mapping = zip(*sorted([ (v, i) for i, v in enumerate(l) ]))
index_list = [ mapping.index(i) for i in range(len(sorted_list)) ]

just replace the call to sorted with your sorting algorithm.

When you set A[i+1]=key, clearly indices[j]=i+1. However, when you set A[i+1]=A[i] You must increment the value of the element of indices that has the value i (because the element of A that was at i is now at i+1). Unfortunately, I think the naive implementation of this algorithm will be O(n^3) in the worst case.

Seems like your idea of changing the indices array while changing the original in order to keep track of them should work. I find that when I sometimes have trouble tracking two indices at once and I'll often resort to stepping through the loop(s) on paper to figure out where I'm going wrong.

I modified your version slightly. It now sorts the list A in place (non descending) and returns a list with the "sorted indices".

def insertionSort(A):
    sorted_indices = [0]
    for j in range(1, len(A)):
        sorted_indices.append(j)
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i+1] = A[i]
            sorted_indices[i+1] = sorted_indices[i]
            i -= 1
        A[i+1] = key
        sorted_indices[i+1] = j
    return sorted_indices

I was trying to solve the same problem, but I was sorting arrays rather than lists. The problem with using sorted was that it returns a list, which for my purposes took up too much memory. Luckily, you can do this with numpy using arrays and argsort:

import numpy
a=numpy.array([1,3,4,2])
p=a.argsort()

Which will give array([0,3,1,2]) as a result. This is sorted low to high.