How do I sort a list with positives coming before negatives with values sorted respectively?

Question

I have a list that contains a mixture of positive and negative numbers, as the following

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

What I am trying to accomplish is to sort the list with the positive numbers coming before the negative numbers, respectively sorted as well.

Desired output:

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

I was able to figure out the first part sorting with the positive numbers coming before the and negative numbers, unfortunately this does not respectively sort the positive and negative numbers.

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] 

How may I achieve my desired sorting with a pythonic solution?

Answer 1

You could just use a regular sort, and then bisect the list at 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] 

The last line here takes advantage of a slice invariant lst == lst[:n] + lst[n:]

Another option would be to use a tuple as a sort key, and rely on lexicographical ordering of 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

Just comparing the different ways.

Results:

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