Блог

Главная - Вопросы по программированию - Сортировка на Python — пузырьков занимает целую вечность

Сортировка на Python — пузырьков занимает целую вечность

#python

Вопрос:

Делаю это для школьного проекта. Мне необходимо:

Выполнение измерений времени выполнения для заданных алгоритмов:

a. Измерения следует производить для случайных наборов из n = 100, 1000, 10000, 100000, 300000

b. Для каждого n сортировка должна повторяться 100 раз, и в конце результаты измерений усредняются:

  • Нарисуйте новый набор чисел для сортировки по количеству элементов n. Диапазон случайных чисел 0 — 10000.
  • Получите время T1.
  • Выполните своего рода случайно выбранный набор.
  • Получите время T2.
  • Выполните вычитание времени T2 — T1 и сохраните результат на множестве измерений

Есть ли какой-нибудь хороший способ ускорить обработку этого кода?

 import time


# bubble_sort
def bubble_sort(array):
    for iter_num in range(len(array) - 1, 0, -1):
        for idx in range(iter_num):
            if array[idx] > array[idx   1]:
                temp = array[idx]
                array[idx] = array[idx   1]
                array[idx   1] = temp


def timing(func, b):
    timingList = list()
    for x in range(100):
        array = [randint(0, 10000) for i in range(b)]
        time1 = time.time()
        func(array)
        time2 = time.time()
        timingList.append(time2 - time1)

    return (sum(timingList) / len(timingList)) * 1000


def imlazy(func):
    print(timing(func, 100))
    print(timing(func, 1000))
    print(timing(func, 10000))
    print(timing(func, 100000))
    print(timing(func, 300000))


if __name__ == '__main__':
    print(imlazy(bubble_sort))

Комментарии:

1. Во-первых, есть ли причина, по которой вы написали timing сами, вместо того, чтобы использовать стандартную timeit библиотеку?

2. Это было в описании задания, чтобы измерить его таким образом.

3. Если они действительно попросили вас 100 раз выполнить сортировку по 300000 значениям, они, вероятно, вас троллят.

4. «сортировка пузырьков занимает целую вечность». Это примерно правильное описание сортировки пузырьков 😉 Используйте любой другой алгоритм сортировки, если хотите повысить производительность.

5. @Grismar Вы хотите сказать, что существуют структуры, более эффективные для сортировки пузырьков, чем списки?

Ответ №1:

Несмотря на общую ужасность пузырькового типа, вот несколько более эффективная реализация:-

 def bubble_sort(L):
    e = len(L)
    while e > 1:
        es = 0
        for i in range(e-1):
            if L[i] > L[i 1]:
                L[i], L[i 1] = L[i 1], L[i]
                es = i 1
        e = es
Метки: