Comment trier une liste en plaçant les valeurs positives avant les négatives, les valeurs étant triées respectivement ?

Question

J'ai une liste qui contient un mélange de nombres positifs et négatifs, comme suit

lst = [1, -2, 10, -12, -4, -5, 9, 2]

Ce que j'essaie d'accomplir, c'est de trier la liste de manière à ce que les nombres positifs viennent avant les nombres négatifs, respectivement triés également.

Sortie souhaitée :

[1, 2, 9, 10, -12, -5, -4, -2]

J'ai réussi à trier la première partie en plaçant les nombres positifs avant les nombres négatifs, mais cela ne permet pas de trier les nombres positifs et négatifs.

lst = [1, -2, 10, -12, -4, -5, 9, 2]
lst = sorted(lst, key=lambda o: not abs(o) == o)
print(lst)

>>> [1, 10, 2, 9, -2, -12, -4, -5]

Comment puis-je réaliser le tri souhaité avec une solution pythonique ?

Answer 1

Vous pourriez simplement utiliser un tri régulier, et ensuite couper la liste en deux à 0 :

>>> lst
[1, -2, 10, -12, -4, -5, 9, 2]
>>> from bisect import bisect
>>> lst.sort()
>>> i = bisect(lst, 0)  # use `bisect_left` instead if you want zeroes first
>>> lst[i:] + lst[:i]
[1, 2, 9, 10, -12, -5, -4, -2]

La dernière ligne ici tire profit d'un invariant de tranche lst == lst[:n] + lst[n:]

Une autre option serait d'utiliser un tuple comme clé de tri, et de se fier à lexicographique l'ordre des tuples :

>>> sorted(lst, key=lambda x: (x<0, x))  # use <= instead if you want zeroes last
[1, 2, 9, 10, -12, -5, -4, -2]

Answer 2

Je compare juste les différentes manières.

Résultats :

> Shuffle cost comparison small
shuffle_lst: 0.001181483967229724
shuffle_ar: 0.014688121969811618
> Shuffle cost comparison medium
shuffle_lst: 0.572294642101042
shuffle_ar: 0.3266364939045161
> Shuffle cost comparison large
shuffle_lst: 26.5786890439922
shuffle_ar: 6.284286553971469

                    +cost               -cost
bisectme:    0.004252934013493359    0.003071450046263635
lexicon:     0.010936842067167163    0.009755358099937439
compreh.:    0.0071560649666935205   0.005974580999463797
arrayme:     0.03787591797299683     0.023187796003185213
nplexicon:   0.022204622975550592    0.007516501005738974
npbisect:    0.023507782025262713    0.008819660055451095

                    +cost               -cost
bisectme:    7.716002315981314   7.143707673880272
lexicon:     22.17862514301669   21.606330500915647
compreh.:    8.690494343056343   8.118199700955302
arrayme:     1.5029839979251847      1.1763475040206686
nplexicon:   2.0811527019832283      1.7545162080787122
npbisect:    1.3076487149810418      0.9810122210765257

                    +cost               -cost
bisectme:    180.77819497592282      154.19950593193062
arrayme:     22.476932613993995      16.192646060022525
nplexicon:   41.74795828794595   35.46367173397448
npbisect:    20.13856932707131   13.85428277309984

Code :

import sys
import numpy as np
from timeit import timeit
from bisect import bisect
from random import shuffle

def shuffle_lst():
    np.random.shuffle(lst)

def shuffle_ar():
    np.random.shuffle(ar)

def bisectme():
    np.random.shuffle(lst)
    lst.sort()
    i = bisect(lst, 0)
    return lst[i:] + lst[:i]

def lexicon():
    np.random.shuffle(lst)
    return sorted(lst, key=lambda x: (x < 0, x))

def comprehension():
    np.random.shuffle(lst)
    return sorted([i for i in lst if i > 0]) + sorted([i for i in lst if i < 0])

def arrayme():
    np.random.shuffle(ar)
    return np.concatenate([np.sort(ar[ar >= 0]), np.sort(ar[ar < 0])], axis=0)

def nplexicon():
    np.random.shuffle(ar)
    return ar[np.lexsort((ar, ar < 0))]

def numpybisect():
    np.random.shuffle(ar)
    ar.sort()
    i = ar.__abs__().argmin()
    return np.concatenate((ar[i:], ar[:i]))

nloops = 1000

lst = list(range(-10**1, 0, 1)) + list(range(10**1, -1, -1))
ar = np.array(lst)
print("> Shuffle cost comparison small")
cost_shuffle_list_small = timeit(shuffle_lst, number=nloops)
print("shuffle_lst:", cost_shuffle_list_small)
cost_shuffle_array_small = timeit(shuffle_ar, number=nloops)
print("shuffle_ar:", cost_shuffle_array_small)

lst = list(range(-10**4, 0, 1)) + list(range(10**4, -1, -1))
ar = np.array(lst)
print("> Shuffle cost comparison medium")
cost_shuffle_list_medium = timeit(shuffle_lst, number=nloops)
print("shuffle_lst:", cost_shuffle_list_medium)
cost_shuffle_array_medium = timeit(shuffle_ar, number=nloops)
print("shuffle_ar:", cost_shuffle_array_medium)

nloops = 100

lst = list(range(-10**6, 0, 1)) + list(range(10**6, -1, -1))
ar = np.array(lst)
print("> Shuffle cost comparison large")
cost_shuffle_list_large = timeit(shuffle_lst, number=nloops)
print("shuffle_lst:", cost_shuffle_list_large)
cost_shuffle_array_large = timeit(shuffle_ar, number=nloops)
print("shuffle_ar:", cost_shuffle_array_large)

print()

nloops = 1000

## With small lists/arrays
lst = list(range(-10**1, 0, 1)) + list(range(10**1, -1, -1))
ar = np.array(lst)

print("\t\t\t\t\tw/o pen.\t\t\t\tw. pen.")

foo = timeit(bisectme, number=nloops)
print("bisectme:\t", foo, "\t", foo - cost_shuffle_list_small)

foo = timeit(lexicon, number=nloops)
print("lexicon:\t", foo, "\t", foo - cost_shuffle_list_small)

foo = timeit(comprehension, number=nloops)
print("compreh.:\t", foo, "\t", foo - cost_shuffle_list_small)

foo = timeit(arrayme, number=nloops)
print("arrayme:\t", foo, "\t", foo - cost_shuffle_array_small)

foo = timeit(nplexicon, number=nloops)
print("nplexicon:\t", foo, "\t", foo - cost_shuffle_array_small)

foo = timeit(numpybisect, number=nloops)
print("npbisect:\t", foo, "\t",  foo - cost_shuffle_array_small)

print()

## With medium lists/arrays
lst = list(range(-10**4, 0, 1)) + list(range(10**4, -1, -1))
ar = np.array(lst)

print("\t\t\t\t\tw/o cost\t\t\t\tw. cost")

foo = timeit(bisectme, number=nloops)
print("bisectme:\t", foo, "\t", foo - cost_shuffle_list_medium)

foo = timeit(lexicon, number=nloops)
print("lexicon:\t", foo, "\t", foo - cost_shuffle_list_medium)

foo = timeit(comprehension, number=nloops)
print("compreh.:\t", foo, "\t", foo - cost_shuffle_list_medium)

foo = timeit(arrayme, number=nloops)
print("arrayme:\t", foo, "\t", foo - cost_shuffle_array_medium)

foo = timeit(nplexicon, number=nloops)
print("nplexicon:\t", foo, "\t", foo - cost_shuffle_array_medium)

foo = timeit(numpybisect, number=nloops)
print("npbisect:\t", foo, "\t",  foo - cost_shuffle_array_medium)

print()

## With large lists/arrays
nloops = 100

lst = list(range(-10**6, 0, 1)) + list(range(10**6, -1, -1))
ar = np.array(lst)

print("\t\t\t\t\tw/o cost\t\t\t\tw. cost")

foo = timeit(bisectme, number=nloops)
print("bisectme:\t", foo, "\t", foo - cost_shuffle_list_large)

foo = timeit(arrayme, number=nloops)
print("arrayme:\t", foo, "\t", foo - cost_shuffle_array_large)

foo = timeit(nplexicon, number=nloops)
print("nplexicon:\t", foo, "\t", foo - cost_shuffle_array_large)

foo = timeit(numpybisect, number=nloops)
print("npbisect:\t", foo, "\t",  foo - cost_shuffle_array_large)

print()

Answer 3

Créez deux listes, une avec les valeurs positives et une autre avec les valeurs négatives, puis triez le contenu de chaque liste comme vous le souhaitez. Par exemple :

my_list = [1, -2, 10, -12, -4, -5, 9, 2]
pos_list, neg_list = [], []
for item in my_list:
    if item < 0: 
        neg_list.append(item)
    else:
        pos_list.append(item)

final_list = sorted(pos_list) + sorted(neg_list)

Answer 4

Vous pourriez simplement trier par le négatif de l'inverse de l'élément :

from __future__ import division

sorted(lst, key=lambda i: 0 if i == 0 else -1 / i)

En prenant l'inverse, on change l'ordre des magnitudes (les plus grands nombres au milieu, les plus petits à l'extérieur). En prenant la négative, on inverse l'ordre (les positifs en premier, les négatifs en dernier).

Faites attention à la taille de vos chiffres, bien sûr, et vérifiez s'ils ne risquent pas de causer des problèmes de dépassement ou d'insuffisance.

Answer 5

Créez deux listes distinctes. Une avec des valeurs positives, l'autre avec des valeurs négatives. Triez la liste négative, puis concaténérez-les ensemble :

>>> lst = [1, -2, 10, -12, -4, -5, 9, 2]
>>> sorted([i for i in lst if i > 0]) + sorted([i for i in lst if i =< 0])
[1, 2, 9, 10, -12, -5, -4, -2]
>>>