0

I have a list of strings

my_string_list = ['Banana', 'Apple', 'Sorry']

How can I check if this my_string_list is sorted or not?

One obvious way is to sort this list and compare it against the original list. But I do not want to iterate over the whole original list to decide that the list is not sorted.

sorted_list_of_strings = sorted(my_string_list)
if my_string_list != sorted_list_of_strings:
    print(f'The list {my_string_list} is not sorted.')

I am wondering if there is any other way to do this?

idkman
  • 169
  • 1
  • 15

1 Answers1

3

Typically, I'd use your solution (if x == sorted(x):) and accept the cost; it's easy to write, and if it's not a hot code path, it hardly matters if you're doing it somewhat inefficiently (for the already-sorted case, it'll be roughly O(n) anyway thanks to Python's TimSort, so you only pay O(n log n) general sort costs for the "not sorted" case). It's also easy to customize when you need to handle reverse sorting, keyed sorting, etc., while remaining easy to write and easy to verify by inspection.

If you want a more efficient solution using Python builtins, you could do something along the lines of (with from operator import le at the top of the file):

if all(map(le, my_string_list, my_string_list[1:])):

which compares each element to the following element, returning False on the first mismatch, and True if they're all less than or equal to the following element. Replace my_string_list[1:] with itertools.islice(my_string_list, 1, None) if you have concerns about the cost (computational or memory cost) of building the temporary list with the plain slice.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • This is not really efficient because `my_string_list[1:]` is a copy. It would be better to iterate elements in pairs, or iterate `range(len(my_string_list))` and index. – wim Aug 13 '21 at 17:30
  • @wim: Better would be to optimize it out with `itertools.islice` or manually making an iterator and advancing it once then using that iterator as the second argument, but it's just an extra `O(n)` step to slice normally, and a relatively cheap `O(n)` step at that. If necessary, `islice(my_string_list, 1, None)` would replace `my_string_list[1:]` to keep it a one-liner, but it's premature optimization unless you're doing this a lot. – ShadowRanger Aug 13 '21 at 17:32
  • 1
    I'm not talking about time-complexity, I'm talking about memory efficiency. – wim Aug 13 '21 at 17:32
  • @wim: Sure. But again, premature optimization in most cases. If your `list` is 10,000 elements long, the incremental cost is temporary consumption of 80 KB (on a 64 bit system); hardly matters (it's always a shallow copy, so the size of the objects stored doesn't matter). `islice` avoids that issue, but I'd skip it unless I knew it was the hottest of code paths and/or the inputs would be huge. I added a note to the answer on that point just to be clear. – ShadowRanger Aug 13 '21 at 17:34
  • @ShadowRanger Awesome! `le` was the functionality I was looking for. – idkman Aug 13 '21 at 17:44
  • 1
    Your code would be just as easy to modify and verify by inspection if you used a generator expression instead of `map`. – Mark Ransom Aug 13 '21 at 17:58
  • @MarkRansom: Sure, `all(first <= second for first, second in zip(my_string_list, my_string_list[1:]))` (or `islice` equivalent) also works just fine. I may leap to `map` a little overly readily sometimes. :-) – ShadowRanger Aug 13 '21 at 18:04