TheAlgorithms-Python

1
from __future__ import annotations
2

3
import re
4

5

6
def natural_sort(input_list: list[str]) -> list[str]:
7
    """
8
    Sort the given list of strings in the way that humans expect.
9

10
    The normal Python sort algorithm sorts lexicographically,
11
    so you might not get the results that you expect...
12

13
    >>> example1 = ['2 ft 7 in', '1 ft 5 in', '10 ft 2 in', '2 ft 11 in', '7 ft 6 in']
14
    >>> sorted(example1)
15
    ['1 ft 5 in', '10 ft 2 in', '2 ft 11 in', '2 ft 7 in', '7 ft 6 in']
16
    >>> # The natural sort algorithm sort based on meaning and not computer code point.
17
    >>> natural_sort(example1)
18
    ['1 ft 5 in', '2 ft 7 in', '2 ft 11 in', '7 ft 6 in', '10 ft 2 in']
19

20
    >>> example2 = ['Elm11', 'Elm12', 'Elm2', 'elm0', 'elm1', 'elm10', 'elm13', 'elm9']
21
    >>> sorted(example2)
22
    ['Elm11', 'Elm12', 'Elm2', 'elm0', 'elm1', 'elm10', 'elm13', 'elm9']
23
    >>> natural_sort(example2)
24
    ['elm0', 'elm1', 'Elm2', 'elm9', 'elm10', 'Elm11', 'Elm12', 'elm13']
25
    """
26

27
    def alphanum_key(key):
28
        return [int(s) if s.isdigit() else s.lower() for s in re.split("([0-9]+)", key)]
29

30
    return sorted(input_list, key=alphanum_key)
31

32

33
if __name__ == "__main__":
34
    import doctest
35

36
    doctest.testmod()
37