Ошибка в написании алгоритма лексикографической сортировки для списка

Question

Задача:

Натуральные числа от 1 до N упорядочены лексикографически. Например, для N=25 результат этого упорядочения будет таким: 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 3, 4, 5, 6, 7, 8, 9.

Требуется написать программу, которая определит, на каком месте оказалось число K.

Входные данные

Входной файл INPUT.TXT содержит два натуральных числа N и K, записанных через пробел (1 ≤ K ≤ N ≤ 10**4).

Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно натуральное число – номер места, на котором оказалось число K.

Например:

Вход: 25 17

Выход: 9

Причина: элемент 17 в списке

[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 3, 4, 5, 6, 7, 8, 9]

находился под номером 9

Мой код:

def lexicographic_sort(arr: list[int]) -> list[int]:
    if len(arr) < 2:
        return arr
    mid = arr[len(arr) // 2]
    l = [i for num, i in enumerate(arr) if str(i) < str(mid) and num != len(arr) // 2]
    r = [i for num, i in enumerate(arr) if str(i) > str(mid) and num != len(arr) // 2]
    return lexicographic_sort(l) + [mid] + lexicographic_sort(r)


n, k = map(int, input().split())
include_list = list(range(1, n + 1))
arr_lexicographic = lexicographic_sort(include_list)
print(arr_lexicographic.index(k) + 1)

Проблема

Один из тестов на сайте не проходит. Где ошибка и как её исправить, чтобы программа работала корректно? Конечно, проще сделать код так и он пройдёт тесты (проверенно):

n, k = map(int, input().split())
include_list = list(range(1, n + 1))
include_list.sort(key=lambda x: str(x))
print(include_list.index(k) + 1)

Меня интересует, где в моей сортировке ошибка.

Сайт, на котором я тестирую: https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=12&id_topic=8&id_problem=38

Answer 1

Не знаю почему, но если брать не элемент по середине, а случайный то все тесты проходит:

import random


def lexicographic_sort(arr: list[int]) -> list[int]:
    if len(arr) < 2:
        return arr
    index = random.randrange(len(arr))
    mid = arr[index]
    l = [i for num, i in enumerate(arr) if str(i) < str(mid) and num != index]
    r = [i for num, i in enumerate(arr) if str(i) > str(mid) and num != index]
    return lexicographic_sort(l) + [mid] + lexicographic_sort(r)


n, k = map(int, input().split())
include_list = list(range(1, n + 1))
arr_lexicographic = lexicographic_sort(include_list)
print(arr_lexicographic.index(k) + 1)

Либо же можно брать всегда первый элемент, так тоже прошёл

Answer 2

Алгоритм вы написали правильный. Но у быстрой сортировки есть неприятная особенность, с которой вы и познакомились.

n = 1999 переполняет стек:

$ echo 1999 1 | python lex_sort.py
Traceback (most recent call last):
  File "lex_sort.py", line 12, in <module>
    arr_lexicographic = lexicographic_sort(include_list)
  File "lex_sort.py", line 7, in lexicographic_sort
    return lexicographic_sort(l) + [mid] + lexicographic_sort(r)
  File "lex_sort.py", line 7, in lexicographic_sort
    return lexicographic_sort(l) + [mid] + lexicographic_sort(r)
  File "lex_sort.py", line 7, in lexicographic_sort
    return lexicographic_sort(l) + [mid] + lexicographic_sort(r)
  [Previous line repeated 993 more times]
  File "lex_sort.py", line 5, in lexicographic_sort
    l = [i for num, i in enumerate(arr) if str(i) < str(mid) and num != len(arr) // 2]
  File "lex_sort.py", line 5, in <listcomp>
    l = [i for num, i in enumerate(arr) if str(i) < str(mid) and num != len(arr) // 2]
RecursionError: maximum recursion depth exceeded while getting the str of an object

При первом разбиении mid = 1000. Такое разбиение очень неравновесное. Налево уходят только три числа 1, 10, 100, направо все остальные.

Распечатка лога print(len(l), mid, len(r)):

len(l)     mid  len(r)

     3    1000    1995
     1      10       1
     1    1002    1993
     0    1003    1992
     0    1004    1991
  1990     999       0
     0    1005    1989
  1988     998       0
     0    1006    1987
  1986     997       0
     0    1007    1985
  1984     996       0
     0    1008    1983
  1982     995       0
     0    1009    1981
  1980     994       0
     1    1010    1978
     0    1011    1977
  1976     993       0
     0    1012    1975
...

В середине массива скопились минимальные и максимальные элементы - 999 и ниже очень велики, 1000 и выше очень малы. Почти всегда при разбиении одна половина остаётся пустой. Глубина стека быстрой сортировки становится линейной. Ошибка.

БЛОГ НА HUSL

Ошибка в написании алгоритма лексикографической сортировки для списка

Ответы (2 шт):