Problem with sorting optimization by Bubble sort method. How to speed up sorting for a list of 100k items?

Question

Python

There is a program for calculating the average value of the sorting time using the Bubble sort method. Condition of the problem: Calculate the average sorting time (it is necessary to measure 10 times). To count time use time.perf_counter() - returns time with maximum precision. The time calculation does not need to include the creation of a random array.
The program does not implement the last condition, it considers the total time for sorting, including the creation of a random array.

import time
import random

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

sred = [0.0] * 5
desyat = 0
sto = 0
tycha = 0
d_t = 0
s_t = 0
spisok = []
for i in range(10):
    for mnog in [10, 100, 1000, 10000, 100000]:
        spisok = [random.randint(1,mnog) for x in range(0,mnog)]
        start = time.perf_counter()
        bubble_sort(spisok)
        if mnog == 10:
            desyat += (time.perf_counter() - start)/10
        if mnog == 100:
            sto += (time.perf_counter() - start)/10
        if mnog == 1000:
            tycha += (time.perf_counter() - start)/10
        if mnog == 10000:
            d_t += (time.perf_counter() - start)/10
        if mnog == 100000:
            s_t += (time.perf_counter() - start)/10
        spisok = []
        print(f'Среднее время выполнения алгоритма списка с 10 элементами: {desyat}')
        print(f'Среднее время выполнения алгоритма списка с 100 элементами: {sto}')
        print(f'Среднее время выполнения алгоритма списка с 1000 элементами: {tycha}')
        print(f'Среднее время выполнения алгоритма списка с 10000 элементами: {d_t}')
        print(f'Среднее время выполнения алгоритма списка с 100000 элементами: {s_t}')

Answer 1

start = time.perf_counter()
bubble_sort(spisok)
end = time.perf_counter()

Didn't it really occur to you that you need to measure time as close as possible to the section of code of interest?

Answer 2

Don't speed up. Bubble sort is slow. Has quadratic execution time. for 100000 elements there will be 5 billion comparisons in the worst case. For random arrays, a couple of times less on average. Given that this is a python, you will have to wait a minute for these 2 billion operations. And taking into account 10 repetitions - all 10 minutes.