все равно будет работать.

ой код - алгоритм пузырьковой сортировки для сортировки элементов списка в порядке asc:

foo = [7, 0, 3, 4, -1]
cnt = 0
for i in foo:
    for i in range(len(foo)-1):
        if foo[cnt] > foo[cnt + 1]:
            temp = foo[cnt]
            c[cnt] = c[cnt + 1]
            c[cnt + 1] = temp
        cnt = cnt + 1
    cnt = 0

Я пересматривал свой код, но он все еще слишком неэффективен для онлайн-судьи. Некоторая помощь будет принята с благодарностью!

 Peyton27 дек. 2017 г., 07:41
Да, это требуется.
 user176775427 дек. 2017 г., 07:41
Bubble sort - пример плохого алгоритма сортировки. Единственное, что вы можете сделать - это ранний выход из цикла, который будет немного быстрее ...
 coldspeed27 дек. 2017 г., 08:13
Если посмотреть на алгоритм, есть возможности для дальнейшего улучшения, если вместо этого вы запустите foo [: - i-1]
 RoadRunner27 дек. 2017 г., 07:44
Вы смотрели на улучшения, которые вы можете сделать, чтобы пузырьковая сортировкаВот, Это не изменит егоO(n**2) сложность, но это немного улучшает его.
 coldspeed27 дек. 2017 г., 07:35
Есть более быстрые алгоритмы сортировки, чем O (n ** 2). Вам нужно использовать пузырьковую сортировку?

Ответы на вопрос(3)

Решение Вопроса
Ранний выходBubbleSortПервый цикл не имеет отношения к тому, что происходит внутриВторой цикл делает всю тяжелую работу. Вы можете избавиться отcount используяenumerateЧтобы поменять элементы, используйте pythonic swap -a, b = b, a.Согласноэтот комментарийИспользуйте ранний выход. Если в любой точке внутреннего цикла нет перестановок, это означает, что список отсортирован, и дальнейшая итерация не требуется. Это интуиция позадиchanged.По определению, после того, как яго итерация внешнего цикла, последнийi элементы будут отсортированы, так что вы можете еще больше уменьшить постоянный коэффициент, связанный с алгоритмом.
foo = [7, 0, 3, 4, -1]
for i in range(len(foo)):
    changed = False
    for j, x in enumerate(foo[:-i-1]):
        if x > foo[j + 1]:
            foo[j], foo[j + 1] = foo[j + 1], foo[j]
            changed = True

    if not changed:
        break

Обратите внимание, что ни одна из этих оптимизаций не меняет асимптотическую (Big-O) сложность BubbleSort (которая остаетсяO(N ** 2)), вместо этого, только уменьшает постоянные факторы, связанные.

чтобы понять, насколько эффективен ваш алгоритм с точки зрения использования вычислительных ресурсов независимо от архитектуры компьютера или тактовой частоты. Это в основном помогает вам анализировать время выполнения или использование памяти вашего алгоритма в худшем случае по мере увеличения размера ввода. Таким образом, время выполнения вашего алгоритма попадет в одну из этих категорий (от самой быстрой до самой медленной);

O (1): постоянное время. Произносится (о 1). Самое быстрое время

O (LG N): логарифмическое время. Произносится (о боже п). Быстрее, чем линейное время. Традиционно это самое быстрое время для поиска.

O (n): линейное время. Произносится (Oh of n, n - размер вашего ввода, например, размер массива). Обычно что-то, когда вам нужно проверить каждый бит вашего ввода.

O (nlgn): самое быстрое время, которое мы можем достичь при выполнении сортировки списка элементов.

O (n ** 2): о n в квадрате. Квадратичное время. Часто это предел, когда у нас есть вложенные циклы.

O (2 ** n): действительно, действительно большой! Число, возведенное в степень n, медленнее, чем n, возведенное в степень.

В вашем случае вы используете вложенные циклы, которые O (n2). Код, который я написал, использует один цикл while и имеет сложность роста O (n), которая быстрее, чем O (n).2). Я действительно не пробовал это на очень большомarray но в вашем случае это похоже на работу. Попробуйте и дайте мне знать, если это работает, как ожидалось.

k = [7, 0, 3, 4, -1]
n = len(k)
i = 0
count = 0
while count < n**2: # assuming we wouldn't go through the loop more than n squared times
    if i == n - 1:
        i = 0
        count += 1
        swapped = False
    elif k[i] > k[i+1]:
        temp = k[i]
        k[i] = k[i+1]
        k[i+1] = temp
        i+=1
        swapped = True
    elif swapped == False:
        i += 1
    elif swapped == True and i < n - 1:
        i += 1

Примечание. В примере списка (k) нам нужно только пройти по списку три раза, чтобы отсортировать его в порядке возрастания. Так что если вы измените цикл while на эту строку кодаwhile count < 4:все равно будет работать.

for i in range(0, len(foo)):
    for j in range(i+1, len(foo)):
        if (foo[i] > foo[j]):
            temp = foo[i]
            foo[i] = foo[j]
            foo[j] = temp

Поскольку вы уже отсортировали все по индексу i, нет необходимости повторять его снова. Это может сэкономить вам более 50% сравнений - в данном случае это 10 против 25 в вашем исходном алгоритме.

Ваш ответ на вопрос