Здравствуйте. У меня проблема в написании программы по вычислению среднего значения времени, затраченного на сортировку списка. Условия задачи:
Для каждого алгоритма сортировки подсчитать среднее (необходимо измерить 10 раз) время выполнения сортировки для 10,100,1000,10000,100000 элементов. Список элементов выбираются рандомно. Алгоритмы:
1)пузырьковая сортировка
Для подсчета времени использовать time.perf_counter() - возвращает время с максимальной точностью. В подсчет времени НЕ нужно включать время создания случайного массива.
Сама проблема состоит в том, что программа слишком долго сортирует. Да, это Bubble sort однако преподаватель говорит что она должна работать не более 40 минут. По моим подсчётам моя программа выдаст результат только по истечению 5-6 часов. Помогите выявить проблемы и нати их решение, пожалуйста.
import time
import random
st4rt_time = time.time()
def bubble_sort(list):
swapped = True
while swapped:
swapped = False
for i in range(len(list) - 1):
if list[i] > list[i + 1]:
list[i], list [i + 1] = list [i + 1], list[i]
swapped = True
m = [10, 100, 1000, 10000, 100000]
for e in m:
for i in range(10):
spisok = [random.randint(0, e) for x in range(0, e)]
time_start = time.perf_counter()
bubble_sort(spisok)
time_start += time.perf_counter() // 10
end = time.perf_counter()
spisok = []
print(f'Время выполнения алгоритма списка с {e} элементами: {time.perf_counter() - time_start}, среднее значение времени: {time_start}')
print("------------------------------------------------Время выполнения программы: %s seconds------------------------------------------------" % round(time.time() - st4rt_time))
Спасибо за поправку в комментариях, теперь прога выглядит так:
import time
import random
st4rt_time = time.time()
def bubble_sort(array):
length = len(array)
for i in range(length):
for j in range(0, length - i - 1):
if array[j] > array[j + 1]:
temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
mean_time = 0
m = [10, 100, 1000, 10000, 100000]
for e in m:
for i in range(10):
spisok = [random.randint(0, e) for x in range(0, e)]
start_time = time.perf_counter()
bubble_sort(spisok)
end_time = time.perf_counter()
elapsed_time = end_time - start_time
mean_time += elapsed_time
mean_time /= 10
print(f"Время работы списка из {e} элементов:{elapsed_time}. Среднее время работы: {mean_time}")
print("------------------------------------------------Время выполнения программы: %s seconds------------------------------------------------" % round(time.time() - st4rt_time))
Однако, остается проблема. Список из 100к элементов всё равно долго рассчитывается. Есть вариант просто умножить значение времени для списка 10к элементов на сто и получится приблизительное время сортировки списка 100к элементов. Остается два вопроса: 1) Как это реализовать чтобы программа сама умножала значение времени 10к списка на 100, а после высчитывала среднее время дял списка 100к?
