Как уменьшить сложность алгоритма обмена для сортировки 5 чисел?

Question

Я практикую сортировку 5 чисел вручную, сравнивая их друг с другом, я должен повторить это n ^ 2 раза, но я хочу уменьшить его.

a1 = 100
a2 = 90
a3 = 45
a4 = 8
a5 = 0
i = 0
while i < 25:
    if a1 > a2:
        tmp = a1
        a1 = a2
        a2 = tmp
    elif a1 > a3:
        tmp = a1
        a1 = a3
        a3 = tmp
    elif a1 > a4:
        tmp = a1
        a1 = a4
        a4 = tmp
    elif a1 > a5:
        tmp = a1
        a1 = a5
        a5 = tmp
    elif a2 > a3:
        tmp = a2
        a2 = a3
        a3 = tmp
    elif a2 > a4:
        tmp = a2
        a2 = a4
        a4 = tmp
    elif a2 > a5:
        tmp = a2
        a2 = a5
        a5 = tmp
    elif a3 > a4:
        tmp = a3
        a3 = a4
        a4 = tmp
    elif a3 > a5:
        tmp = a3
        a3 = a5
        a5 = tmp
    elif a4 > a5:
        tmp = a4
        a4 = a5
        a5 = tmp
    i = i + 1
print(a1, a2, a3, a4, a5)

Код способен сортироватьчисла, но, как вы можете видеть цикл I работает до 25 раз, чтобы отсортировать все числа.

Answer 1

Мне просто интересно, может ли этот код быть более оптимальным ...

Код представляет собой пузырьковую сортировку.Код должен зацикливаться только 4 раза, а не 25 раз.Код перемещает самый большой элемент в a5 в первом цикле, затем в следующий самый большой элемент в a4 во втором цикле, затем в a3 в третьем цикле и в a2 в четвертом цикле, оставляя наименьшее в a1.Развертывание цикла для пузырьковой сортировки требует 10 операций сравнения и обмена:

if a1 > a2: a1,a2 = a2,a1
if a2 > a3: a2,a3 = a3,a2
if a3 > a4: a3,a4 = a4,a3
if a4 > a5: a4,a5 = a5,a4
if a1 > a2: a1,a2 = a2,a1
if a2 > a3: a2,a3 = a3,a2
if a3 > a4: a3,a4 = a4,a3
if a1 > a2: a1,a2 = a2,a1
if a2 > a3: a2,a3 = a3,a2
if a1 > a2: a1,a2 = a2,a1

---

Это можно уменьшить до 9 операций сравнения и обмена с использованием одной из 180 возможных сетей сортировки для 5 элементов.Оптимизация процессора может выполнять некоторые сравнения и замены параллельно, если операции независимы (не включают одни и те же переменные):

if a1 > a2: a1,a2 = a2,a1
if a3 > a4: a3,a4 = a3,a4
if a1 > a3: a1,a3 = a3,a1
if a2 > a5: a2,a5 = a5,a2
if a1 > a2: a1,a2 = a2,a1
if a3 > a4: a3,a4 = a3,a4
if a2 > a3: a2,a3 = a3,a2
if a4 > a5: a4,a5 = a4,a5
if a3 > a4: a3,a4 = a3,a4

---

По аналогии со ссылкой в ​​ответе Саюджа Самуэля, используяВ результате сочетания перестановок и вставок число сравнений может быть уменьшено с 9 до 7, но это по-прежнему максимум 18 назначений, которые будут перестановками или перемещениями в других языках программирования, операторы else приведут к безусловным переходам на большинстве процессоров, иесть больше зависимостей последовательности, поэтому это может быть медленнее, чем сортировка сети.

if a1 > a2:      a1,a2       = a2,a1
if a3 > a4:      a3,a4       = a4,a3
if a1 > a3:      a1,a2,a3,a4 = a3,a4,a1,a2
if a3 > a5:
    if a1 > a5:  a1,a3,a4,a5 = a5,a1,a3,a4
    else:        a3,a4,a5    = a5,a3,a4
else:
    if a4 > a5:  a4,a5 = a5,a4
if a2 > a4:
    if a2 > a5:  a2,a3,a4,a5 = a3,a4,a5,a2
    else:        a2,a3,a4,a5 = a3,a4,a2,a5
else:
    if a2 > a3:  a2,a3       = a3,a2

Answer 2

Как уже предлагали другие, этот алгоритм не очень хорош - но вы могли бы сделать код лучше (что, как я понимаю, это то, что вы просите).

вместо того, чтобы использовать временную переменную длясвоп, вы можете

a1, a2 = a2, a1

покончить с тремя строками.

также вместо

i = 0
while i < 25
    ...
    i += 1

вы можете использовать

for i in range(25):
    ...

, что более элегантно.

Answer 3

Merge Sort идеально подходит для общих случаев, так как порядок nlogn для лучших, средних и худших случаев.Но я предлагаю иное, потому что Merge Sort не будет лучше, чем просто O(n^2) для сортировки всего 5 элементов.

Если вы ищете эффективный способ сортировки этих 5 чисел в самые короткие шагивозможно, тогда вы могли бы найти этот ответ полезным.Здесь 5 чисел отсортированы всего за 7 шагов (наихудший случай).Принимая во внимание, что даже процедура Merge Sort занимает не менее 8 шагов (забудьте комплексный код для сортировки слиянием).

Массив сортировки из 5 целых чисел с макс. 7 сравнениями (https://cs.stackexchange.com/a/10969)

Answer 4

Вы используете алгоритм, который имеет временную сложность O(n^2).

Вам нужно использовать более быстрые алгоритмы, такие как Merge sort или Quick sort.Но для ранее отсортированных данных Quick sort даст плохую производительность, поэтому я предлагаю использовать Merge sort здесь.

Также вы можете использовать алгоритм Count sort, но иногда это не очень хорошее решение.

Итак, изучите алгоритм сортировка слиянием и используйте его, чтобы получить O(nlogn) сложность времени!