A scanner names its files like "Roll2_img10.jpg". Sorted as plain strings, "img10" lands before "img9", which annoys everyone. Write natural_sort(names: list[str]) -> list[str] that returns a new list in "natural" order:
- Split each name into chunks: maximal runs of digits (
0-9) and maximal runs of everything else."Roll2_img10.jpg"becomes"Roll","2","_img","10",".jpg". - Compare two names chunk by chunk, left to right, at the first chunk where they differ:
- two digit chunks compare by numeric value (
"9" < "10", and"007"equals"7"); - two text chunks compare case-insensitively (compare their
.lower()); - a digit chunk sorts before a text chunk.
- two digit chunks compare by numeric value (
- If one name's chunks run out first while all its chunks matched, the shorter name comes first.
- If two names are still tied after that (e.g.
"a07"and"a7", or"B1"and"b1"), break the tie by plain string comparison of the whole names.
natural_sort(["img10.jpg", "img9.jpg", "IMG2.jpg", "img2.JPG"])
# ["IMG2.jpg", "img2.JPG", "img9.jpg", "img10.jpg"]
natural_sort(["a7", "a07", "a", "7a"])
# ["7a", "a", "a07", "a7"]
0 <= len(names) <= 10^5; each name has 0 to 30 printable ASCII characters. Names may repeat.- Don't change the list you were given.
Show hint
build a key per name with re.findall(r"\d+|\D+", name), turning each chunk into a tuple such as (0, int(chunk), "") for digits and (1, 0, chunk.lower()) for text so every chunk has the same shape; the whole key is (list_of_chunk_tuples, name).