Arrange the list in sequence

Question

I have a list {10,5,3,9,12}. I need to convert it into like this {3,1,0,2,4}.I mean assign 0 to smallest value,1 to next smallest value so on.

my code:

     list = {2,3,10,5,1};
     for (int i =list.Count-1; i >= 0 ; i--)
        {

            var maxNo = list.Max();
            var smallIndex = list.IndexOf(maxNo);
            list[smallIndex] = i * -1;

        }
        for (int i = 0; i < list.Count; i++)
        {
            list[i] = list[i] * -1;
        }
        // prints {1,2,4,3,0}

Note: List will contain positive numbers only.

Is above code is fine. Need help on this.

Answer 1

Essentially you just need to sort the list. Look at sorting algorithms.

You can construct another list containing your original numbers paired with integer indices from 0 to the length of the list, like {{10,0}, {5，1}, {3,2}, {9,3}, {12,4}}, sort this list using your programming language's built-in sort function, then extract the integer indices.

EDIT: Your program will work, but it's rather hackish (using those negative numbers), and very inefficient. It traverses the list twice for every element to find the maximum and to find the index of the maximum. I'd suggest you read about sorting algorithms a bit.

EDIT2: A practical implementation of this might mean using a different comparison function for sort: Assume your original list is called array. Make another array idx = {0,1,2,3,4}, and sort it not based on a comparison function x < y but array[x] < array[y].

CORRECTION

The algorithms here finds the inverse permutation of what is needed. As Don mentioned you'll need to do another sort to invert the permutation.

Answer 2

this is O(2 (n log n)) as it sorts twice. first it turns the list into a list of (index, value) sorts that by value v and adds the sorted positions s and sorts by index and then extracts the sorted positions.

>>> list( s for s, i in sorted( ( (s,i) for s,(i,v) in enumerate(sorted( ( (i,v) for i,v in enumerate([10,5,3,9,12]) ), key=lambda t: t[1] )) ), key=lambda t: t[1] ) )
[3, 1, 0, 2, 4]

or on multiple lines (note that this may retain memory for longer than is required):

def arrange(l):
    a = sorted( ( (i,v) for i,v in enumerate(l) ), key=lambda t: t[1] )
    b = sorted( ( (s,i) for s,(i,v) in enumerate(a) ), key=lambda t: t[1] )
    return list( s for s, i in b )

print arrange([10,5,3,9,12])

Answer 3

Your algorithm works for a list of non-negative integers, but as others have noted, it's not efficient because of the repeated max calculation.

I'm not sure I'm adding much here, as Dan D's answer is correct, but maybe a little more explanation will help a bit ...

What you're looking for in your example of {2,3,10,5,1} mapping to {1,2,4,3,0} is a list of the indices that your original list would occupy in a sorted list.

The most natural way to get that is by sorting, indexing, and "unsorting" as follows (and as implemented in Dan D's somewhat terser solution):

Add an index column to your original data:

{2,3,10,5,1} => {(2,0), (3,1), (10,2), (5,3), (1,4)}

Sort this by the original column:

{(2,0), (3,1), (10,2), (5,3), (1,4)} => {(1,4), (2,0), (3,1), (5,3), (10,2)}

Add another index column:

{(1,4), (2,0), (3,1), (5,3), (10,2)} => {(1,4,0), (2,0,1), (3,1,2), (5,3,3), (10,2,4)}

Get back to the original order by sorting on the first index column:

{(1,4,0), (2,0,1), (3,1,2), (5,3,3), (10,2,4)} => {(2,0,1), (3,1,2), (10,2,4), (5,3,3), (1,4,0)}

Drop the original column and the first index column, keeping only the index added in the middle, which has now been put into the right position:

{(2,0,1), (3,1,2), (10,2,4), (5,3,3), (1,4,0)} => {1,2,4,3,0}

This strategy will work regardless of the data type of the original list, as long as it's something that can be sorted.

As the problem definitely has to involve some sorting, I strongly doubt you can do better than this for efficiency. Adding and dropping the columns is linear, and sorting twice is not significantly worse than sorting once.