Проблема с оптимизацией сортировки методом Bubble sort. Как ускорить сортировку для списка из 100 тысяч элементов?

Question

[mestniy_tatarin]

Есть программа для вычисление среднего значения времени сортировки методом Bubble sort. Условие задачи: Вычислить среднее время выполнения сортировки (необходимо измерить 10 раз). Для подсчета времени использовать time.perf_counter() - возвращает время с максимальной точностью. В подсчет времени не нужно включать время создание случайного массива.
В программе не реализовано последнее условие, оно считает общее время выполнения сортировки в том числе и с созданием случайного массива.

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

[Vindicar]

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

Неужели в голову не пришло, что нужно замерять время как можно ближе к интересующему участку кода?

Comments

[mestniy_tatarin]

Извините, я новичок, спасибо вам за решение моей проблемы, очень благодарен

[pfg21]

mestniy_tatarin, отметь его ответ решением тогда уж

Answer 2

[Wataru]

Никак не ускорить. Сортировка пузырьком - медленная. Имеет квадратичное время выполнения. для 100000 элементов там будет 5 миллиардов сравнений в худшем случае. Для случайных массивов в пару раз меньше в среднем. С учетом, что это питон - вам этих 2х миллиардов операций придется ждать минуту. А с учетом 10 повторений - все 10 минут.

Comments

[mestniy_tatarin]

Разрешите спросить, а сортировка выбором и вставками в подобной программе только с другой функцией будет быстрее?

[Wataru]

mestniy_tatarin, Почитайте в википедии, или в учебнике у вас - какая у них временная сложность. Если O(n^2) - то будет также медленно. Если O(n log n) - то будет быстрее.

[Andrey]

Wataru , почему ни как ?
Вот есть хорошая статья на эту тему https://habr.com/ru/post/204600/