CODEWITHSUNDEEP
algorithm
Hukam
Hukam

Reputation: 1026

Arrange the list in sequence

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.

Upvotes: 5

Views: 339

Answers (5)

Dan D.
Dan D.

Reputation: 74655

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])

Upvotes: 3

Marcin
Marcin

Reputation: 49846

Sort a copy of the list, put it into a keyed datastructure with list items as keys, and the position in the sorted list as the value. Map the original list using the keyed datastructure. knlogn + 2n = O(nlogn) performance.

Upvotes: 0

Don Roby
Don Roby

Reputation: 41137

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.

Upvotes: 2

Szabolcs
Szabolcs

Reputation: 25703

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.

Upvotes: 5

xpda
xpda

Reputation: 15813

This will work, but using list.IndexOf(maxNo) once for each item results in time of O(n^2). It would be more efficient to sort the list, except maintain an index array such that ix[i] is the ith largest item. In other words, compare list[i], but assign ix[i] in the sort. This will also work with negative numbers.

Upvotes: 1

Related Questions