0

numpy.argsort returns a sorted list to perform an indirect sorting, but it doesn't seem to accept a user-defined function to compare two elements.

I wonder how one can get the sorted list based on a comparison with a user-defined function.

In my case, I have a table of results:

a = [[1,2,3,5,6,7,8],[4,6,2,5,6,3,4],...]

And my function to compare is:

def argMedian(A):
    s   = np.array([sum(A[:i+1]) for i in range(Nmentions)])
    mid = float(s[Nmentions-1])/2
    return np.argwhere(mid < s)[0][0]

def tieBreaking(A, B):
Ac = A
Bc = B
medA = argMedian(Ac)
medB = argMedian(Bc)
while medA == medB:
    Ac[medA] -= 1
    Bc[medB] -= 1
    medA = argMedian(Ac)
    medB = argMedian(Bc)
return 1 if medA > medB else -1

This is an implementation of the majority judgment. A list contains the number of votes for each grade. In case of the median between two lists is equal, a median vote is deleted for both lists and the comparison of the median is again tested. Here, I consider index 0 as the best grade and index 7 as the worst.

I need to perform an indirect sorting, because I want to know the ranking.

guhur
  • 2,500
  • 1
  • 23
  • 33
  • That comparison function doesn't make sense, because you're using the median as an index into the list, but the median of the values may not be a valid index. Also, even if it worked, it would mutate your lists, which is probably not what you want. Please describe how you want to sort your lists. – BrenBarn Mar 06 '16 at 22:12
  • Hum, I think that the ceiling of the median provides a valid index as soon as all values are not equal no? To avoid mutating the lists, I should first copy them? The idea is to implement the tie-breaking algorithm from a majority jugdment: https://en.wikipedia.org/wiki/Majority_judgment#Example_application – guhur Mar 06 '16 at 22:17
  • 2
    If your list is `[100, 200, 300]`, then the ceiling of the median is 200, but 200 is not a valid index into the list. – BrenBarn Mar 06 '16 at 22:19
  • Also, the algorithm described on that page does not involve modifying individual values (as you seem to be trying to do here by subtracting 1 from certain values). Rather, it *removes* values from the list of votes. – BrenBarn Mar 06 '16 at 22:24
  • Right. I have updated the implementation and brought more information on the context – guhur Mar 06 '16 at 22:33
  • I have found this: http://stackoverflow.com/questions/3382352/equivalent-of-numpy-argsort-in-basic-python. Using their results, what can be done is: `sorted(range(len(results)), cmp=tieBreaking, key=results.__getitem__)` where `results` is the table of results of the vote – guhur Mar 06 '16 at 22:43

3 Answers3

1

If you are using Python >= 3.4, you can use statistics.median_low().

from random import randrange
from statistics import median_low

a = [[randrange(8) for _ in range(7)] for _ in range(10)]

print("unsorted")
for item in a:
    print(item)

a.sort(key=median_low)

print("\nsorted")
for item in a:
    print(item)

output:

unsorted
[4, 2, 2, 1, 4, 7, 4]
[2, 2, 2, 7, 5, 5, 6]
[3, 0, 0, 5, 5, 3, 1]
[4, 7, 6, 2, 6, 7, 3]
[4, 7, 7, 1, 2, 7, 7]
[6, 2, 6, 5, 6, 7, 2]
[7, 1, 6, 0, 0, 7, 1]
[0, 5, 1, 2, 1, 7, 7]
[2, 7, 6, 7, 5, 4, 7]
[6, 5, 2, 3, 5, 0, 3]

sorted
[7, 1, 6, 0, 0, 7, 1]
[0, 5, 1, 2, 1, 7, 7]
[3, 0, 0, 5, 5, 3, 1]
[6, 5, 2, 3, 5, 0, 3]
[4, 2, 2, 1, 4, 7, 4]
[2, 2, 2, 7, 5, 5, 6]
[4, 7, 6, 2, 6, 7, 3]
[6, 2, 6, 5, 6, 7, 2]
[2, 7, 6, 7, 5, 4, 7]
[4, 7, 7, 1, 2, 7, 7]

EDIT full alternate solution:

Consider sorting a list as follows: 1. Find the median_low of the list and move it to the front of the list 2. Find the median_low of list[1:] and move it to the second spot 3. Find the median_low of list[2:] ...

You can sort the original lists by median values, or create keys in which the elements are sorted by median values.

def def keyfunc(x):
    t = x[:]
    return [t.pop(t.index(median_low(t))) for _ in range(len(t))]

a = [
    [4, 2, 2, 1, 4, 7, 4],
    [2, 2, 2, 7, 5, 5, 6],
    [3, 0, 0, 5, 5, 3, 1],
    [7, 1, 6, 0, 0, 6, 1],    # tie for first four rounds, but then wins
    [4, 7, 6, 2, 6, 7, 3],
    [6, 2, 6, 5, 6, 7, 2],
    [7, 1, 6, 0, 0, 7, 1],    # tie for first four rounds
    [0, 5, 1, 2, 1, 7, 7],
    [2, 7, 6, 7, 5, 4, 7],
    [6, 5, 2, 3, 5, 0, 3]
]

a.sort(key=keyfunc)

print("\nsorted")
for item in a:
    print(item)

output:

sorted
[7, 1, 6, 0, 0, 6, 1]
[7, 1, 6, 0, 0, 7, 1]
[0, 5, 1, 2, 1, 7, 7]
[3, 0, 0, 5, 5, 3, 1]
[6, 5, 2, 3, 5, 0, 3]
[4, 2, 2, 1, 4, 7, 4]
[2, 2, 2, 7, 5, 5, 6]
[4, 7, 6, 2, 6, 7, 3]
[6, 2, 6, 5, 6, 7, 2]
[2, 7, 6, 7, 5, 4, 7]
RootTwo
  • 4,288
  • 1
  • 11
  • 15
  • This is a good idea, but in case of equality, the algorithm of tie breaking throws away a grade. Unfortunately, no built-in function can do that. – guhur Mar 07 '16 at 16:17
  • 1
    As the wikipeadia page says: if there is a tie for winner, take the the ones that tied, delete the median value, and sort them again. Repeat until you have a winner. Use `list.remove()` to remove an specific value from a list. – RootTwo Mar 07 '16 at 16:22
0

You don't need to use numpy to sort the elements of your list. You can the sort() fuctions for lists or sorted(). Define your custom comparator there if needed.

Stephen Grimes
  • 398
  • 1
  • 7
  • Actually I really need to perform an indirect sorting: what I want is to know the index to sort, not the result of the sorting – guhur Mar 06 '16 at 22:34
0

For computing an indirect sorting with basic python, few tricks exist. They were compared in Equivalent of Numpy.argsort() in basic python?.

Taking the fastest solution, one can add a comparison function.

In Python 2.7:

sorted(range(len(results)), cmp=tieBreaking, key=results.__getitem__)

In Python 3, one should take care that cmp has disappeared, but the function cmp_to_key can replace it.

Community
  • 1
  • 1
guhur
  • 2,500
  • 1
  • 23
  • 33