Здравейте, сега уча два курса едновременно. Python и алгоритми. Започнах сам да решавам алгоритмите. След като достигна до решение, сравнявам кода. Сега правя Bubble Sort и се натъкнах се на нещо любопитно:

Първото решения е моя код, който не е оптимизиран. Винаги върти от първия до последния елемент в масива. Тоест, дори масива да е вече сортиран, винаги прави максималните обхождания. Тайминга е 1.4 - 1.8 мс.

Второто решение е от интернет. Тайминга е 6.5 - 8.2 мс. Приблизително 5 -6 пъти по бавно.

Третото решение е моят код с оптимизация за вече сортиран масив. Тайминга е почти същия, като този на решение 2.

Въпросът ми е: Дали забавянето идва от инициализацията на булева стойност. И след като тайминга е един от основните критерии за един алгоритъм, не е ли това немислимо(5 -6 пъти по- бавно изпълнение)?

import time


def bubble_sort(array):
    for i in range(0, len(array) - 1):
        for j in range(0, len(array) - 1):
            temp = j + 1
            if array[temp] < array[j]:
                array[j], array[temp] = array[temp], array[j]


# def bubble_sort(array):
#     arr_sorted = False
#     while not arr_sorted:
#         arr_sorted = True
#         for i in range(0, len(array) - 1):
#             if array[i] > array[i + 1]:
#                 arr_sorted = False
#                 array[i], array[i + 1] = array[i + 1], array[i]


# def bubble_sort(array):
#     arr_sorted = True
#     for i in range(0, len(array) - 1):
#         for j in range(0, len(array) - 1):
#             temp = j + 1
#             if array[temp] < array[j]:
#                 arr_sorted = False
#                 array[j], array[temp] = array[temp], array[j]
#         if arr_sorted:
#             break


array_list = [17, 20, 26, 31, 44, 54, 55, 77, 93]
start_time = time.clock()
bubble_sort(array_list)
print(time.clock() - start_time, "seconds")
print(array_list)

П.С

Поправям се. Забавянето идва от масива. Сортирания масив е по бавен от несортирания...

array_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]