Линейная сортировка списков с 2 элементами

Question

Это мой первый вопрос, поэтому я принимаю любые / все советы, если мой вопрос сформулирован неправильно.

Прежде всего, проблема:

Скажем, у нас есть следующий массив A= [(1, 'кошка'), (1, 'собака'), (0, 'жираф'), (0, 'гепард'), (1, 'слон')]]

Мне нужноиспользовать алгоритм, который будет сортировать этот список на основе первого элемента каждого компонента (имеется в виду число).В частности, упоминается, что он не обязательно должен быть устойчивым алгоритмом (я полагаю, это означает, что нам не нужно рассматривать сортировку слов после числа, только нули перед всеми 1)

IТакже следует упомянуть, что я не хочу использовать стратегии создания боковых массивов, которые я буду заполнять результатами по мере их сортировки алгоритмом.Требуется, чтобы алгоритм сортировал массив в том же массиве.

Код, который я разработал, следующий:

def SwapAround(A, start, end):
start_pos = start

for i in range(start,end):
    if A[i] < A[end]:
        A[i], A[start_pos] = A[start_pos], A[i]
        start_pos = start_pos + 1
A[start_pos], A[end] = A[end], A[start_pos]

return start_pos


A=[(1,'cat'),(0,'dog'),(1,'kangaroo'),(0,'mule'),(1,'giraffe'),(1,'dog'), 
(0,'bat')]
SwapAround(A,0,len(A) - 1)
print(A)

У меня довольно специфические проблемы с ним, хотя яЯ вполне уверен, что он должен работать (по крайней мере, шаг за шагом, код имел смысл для меня).

Код сортирует список, но не полностью ... например, мой последнийвывод был:

[(0, 'bat'), (0, 'dog'), (1, 'kangaroo'), (0, 'mule'), (1, 'giraffe'), (1, 'dog'), (1, 'cat')]

С меньшим списком он действительно сработал, и я удивился, когда проснулся этим утром, чтобы добавить еще пару компонентов в свой список, и он не работает.

Не могли бы вы сказать мне, если вы видите что-то легко «неправильное», что я должен рассмотреть, и обоснование этого, чтобы я мог полностью понять это.

Второй вопрос: если бы я хотел добавить компоненты к своемусписок, который также имеет число 2 (то есть мой алгоритм должен будет сортировать между 0,1,2 вместо 0 и 1), если бы вы использовали совершенно другой алгоритм или плечобуду обмениваться еще работать?Первоначально я думал, что обмен не будет работать должным образом (и это не работает с этим алгоритмом), и, возможно, CountingSort или RadixSort будут работать лучше, поэтому ваш вклад будет очень признателен.

Answer 1

Ваш алгоритм концептуально неверен, хотя он уже близок к решению.

Важная проблема вашего алгоритма состоит в том, что изменится только первый элемент, подлежащий обмену.Вместо этого вам нужно переместить как индекс последнего, так и первого элемента.

def sort_binary_key(arr):
    l, u = 0, len(arr) - 1

    while l < u:
        if arr[l] == 1 and arr[u] == 0:
            arr[l], arr[u] = arr[u], arr[l]
        elif arr[l] == 1:
            u -= 1
        elif arr[u] == 0:
            l += 1
        else:
            u -= 1
            l += 1

Для второй части вопроса:
Да, это возможно.Запустите приведенный выше алгоритм дважды.В первом запуске переместите все элементы с 0 в нижнюю часть массива, все остальные элементы - в верхнюю.Затем запустите тот же алгоритм для второй части массива, сортируя элементы с 1 и 2 в качестве первого члена кортежа.

def sort_binary_key(arr, l, u, key_mapper):
    while l < u:
        al, au = key_mapper(arr[l]), key_mapper(arr[u])

        if al == 1 and au == 0:
            arr[l], arr[u] = arr[u], arr[l]
        elif al == 1:
            u -= 1
        elif au == 0:
            l += 1
        else:
            u -= 1
            l += 1

    return l

def sort_ternary(arr):
    tmp = sort_binary_key(arr, 0, len(arr) - 1, lambda t: 0 if t == 0 else 1)
    sort_binary_key(arr, tmp, len(arr) - 1, lambda t: 0 if t == 1 else 1)

Обратите внимание, что приведенный выше код предназначен только для демонстрации.Этот код работает со списками целых чисел вместо входных данных, предоставленных OP.

Answer 2

Ваш алгоритм не может работать на гораздо более глубоком уровне.Вы используете алгоритм общей сортировки сложности O (n) .Не существует алгоритма для общей сортировки с такой средней сложностью (если вы ее найдете, дайте мне знать!).Проверьте эту таблицу сложностей различных алгоритмов сортировки.

Если ваш сценарий только с 0 и 1, и вы хотите, чтобы все 0 в начале и 1 в конце (нестабильно), то это можно сделать с помощью O (n) (проверьте Ответ Павла , чтобы увидеть, как это сделать), и ваш алгоритм совершенно иным.

---

Вы можете использовать список питонов sort и просто передатьключ:

A = [(1,'cat'), (1,'dog'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]
sorted(A, key=lambda x: x[0])
>>> [(0, 'giraffe'), (0, 'cheetah'), (1, 'cat'), (1, 'dog'), (1, 'elephant')]

Вы также можете сделать это с учетом вторичного ключа (имя и второе число):

B = [(1,'cat'), (0,'cat'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]
sorted(B, key=lambda x: (x[1], x[0]))
>>> [(0, 'cat'), (1, 'cat'), (0, 'cheetah'), (1, 'elephant'), (0, 'giraffe')]

Python имеет сортировку по умолчанию и вВ вашем случае вы можете просто написать:

C = [(1,'cat'), (0,'cat'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]
sorted(C)
>>> [(0, 'cat'), (1, 'cat'), (0, 'cheetah'), (1, 'elephant'), (0, 'giraffe')]