Неправильная реализация сортировки вставок или неправильное понимание сложности времени?

Question

Я написал несколько сценариев Python для тестирования и определения времени различных распространенных алгоритмов, исключительно для собственного назидания.Я уверен, что уже есть ресурсы, которые сделали это, но я считаю полезным написать их самостоятельно.

Я написал скрипт, который реализует пузырьковую сортировку, выборку и вставку, и для каждого из них.он запускает 10 итераций переменных размеров массива, а также лучший / худший / средний порядок массивов.

В большинстве случаев я вижу то, что ожидал, например, сортировка выборки всегда занимает одно и то же время независимо от порядкамассива, и пузырьковая сортировка работает ужасно, как и ожидалось.Я также вижу, что производительность сортировки вставкой улучшается по мере улучшения порядка данного массива, однако меня смущает сравнение выбора и вставки.

Я знаю, что оба алгоритма имеют сложность времени наихудшего случая:O (n ^ 2), и что средняя сложность по времени для сортировки вставкой лучше, чем сортировка выбора, но я вижу, что во многих случаях сортировка вставки работает хуже, чем сортировка выбора, что мне кажется неправильным.Я ожидал бы, что эти два будут выполнять то же самое в худшем случае, и эта сортировка вставки будет работать лучше, когда не худший случай.Я неправильно понимаю, как интерпретировать эти результаты, или я допустил ошибку в моей реализации двух алгоритмов?

Вот мой сценарий:

import random
import time
import sys
from enum import Enum

class Case(Enum):
    BEST = 1
    WORST = 2
    AVERAGE = 3

def bubble_sort(arr):
    sorted = False
    while not sorted:
        sorted = True
        for i in range(0, len(arr)):
            # n
            if i + 1 < len(arr) and arr[i] > arr[i + 1]:
                scratch = arr[i]
                arr[i] = arr[i + 1]
                arr[i + 1] = scratch
                sorted = False
    return arr

def selection_sort(arr):
    for i in range(0, len(arr)):
        # n
        min_index = i
        for j in range(i + 1, len(arr)):
            # n
            if arr[j] < arr[min_index]:
                min_index = j
        scratch = arr[i]
        arr[i] = arr[min_index]
        arr[min_index] = scratch
    return arr

def insertion_sort(arr):
    for i in range(1, len(arr)):
        # n
        index = i
        while index > 0 and arr[index - 1] > arr[index]:
            # worst case n, best case 1
            scratch = arr[index]
            arr[index] = arr[index - 1]
            arr[index - 1] = scratch
            index -= 1
    return arr

TOTAL_RUNS = 10

def verify(algorithm, name):

    # first let's test that it actually sorts correctly
    arr = list(range(1, 20))
    random.shuffle(arr)
    arr = algorithm(arr)
    for i in range(0, len(arr) - 1):
        if arr[i] > arr[i + 1]:
            raise Exception("NOT SORTED!")

    print("timing " + name + " sort...")

    def time_the_algorithm(algorithm, case):
        total = 0
        min = sys.maxsize
        max = 0

        sizes = [1000,5000,10000]

        for size in sizes:
            for i in range(0, TOTAL_RUNS):

                arr = list(range(1, size))
                if case == Case.WORST:
                    # for worst case, reverse entire array
                    arr = list(reversed(arr))
                elif case == Case.AVERAGE:
                    # average case, random order
                    random.shuffle(arr)

                start = time.time()
                arr = algorithm(arr)
                end = time.time()

                elapsed = end - start
                total += elapsed
                if elapsed > max:
                    max = elapsed
                if elapsed <= min:
                    min = elapsed

            print(name + ", n={0:} - ".format(size) + str(case) + ": avg {0:.2f}s, min {1:.2f}s, max {2:.2f}s".format(total/TOTAL_RUNS, min, max))

    # worst case
    time_the_algorithm(algorithm, Case.WORST)
    # avg case
    time_the_algorithm(algorithm, Case.AVERAGE)
    # best case
    time_the_algorithm(algorithm, Case.BEST)


verify(insertion_sort, "insertion")
verify(selection_sort, "selection")
verify(bubble_sort, "bubble")

И вот мой вывод:

timing insertion sort...
insertion, n=1000 - Case.WORST: avg 0.06s, min 0.06s, max 0.06s
insertion, n=5000 - Case.WORST: avg 1.42s, min 0.06s, max 1.46s
insertion, n=10000 - Case.WORST: avg 6.90s, min 0.06s, max 5.70s
insertion, n=1000 - Case.AVERAGE: avg 0.03s, min 0.03s, max 0.03s
insertion, n=5000 - Case.AVERAGE: avg 0.71s, min 0.03s, max 0.70s
insertion, n=10000 - Case.AVERAGE: avg 3.44s, min 0.03s, max 2.76s
insertion, n=1000 - Case.BEST: avg 0.00s, min 0.00s, max 0.00s
insertion, n=5000 - Case.BEST: avg 0.00s, min 0.00s, max 0.00s
insertion, n=10000 - Case.BEST: avg 0.00s, min 0.00s, max 0.00s
timing selection sort...
selection, n=1000 - Case.WORST: avg 0.02s, min 0.02s, max 0.02s
selection, n=5000 - Case.WORST: avg 0.43s, min 0.02s, max 0.43s
selection, n=10000 - Case.WORST: avg 2.17s, min 0.02s, max 1.84s
selection, n=1000 - Case.AVERAGE: avg 0.01s, min 0.01s, max 0.02s
selection, n=5000 - Case.AVERAGE: avg 0.43s, min 0.01s, max 0.44s
selection, n=10000 - Case.AVERAGE: avg 2.30s, min 0.01s, max 1.93s
selection, n=1000 - Case.BEST: avg 0.01s, min 0.01s, max 0.02s
selection, n=5000 - Case.BEST: avg 0.42s, min 0.01s, max 0.41s
selection, n=10000 - Case.BEST: avg 2.26s, min 0.01s, max 1.92s
timing bubble sort...
bubble, n=1000 - Case.WORST: avg 0.11s, min 0.11s, max 0.11s
bubble, n=5000 - Case.WORST: avg 3.15s, min 0.11s, max 3.24s
bubble, n=10000 - Case.WORST: avg 15.09s, min 0.11s, max 13.66s
bubble, n=1000 - Case.AVERAGE: avg 0.09s, min 0.09s, max 0.10s
bubble, n=5000 - Case.AVERAGE: avg 2.62s, min 0.09s, max 2.63s
bubble, n=10000 - Case.AVERAGE: avg 12.53s, min 0.09s, max 10.90s
bubble, n=1000 - Case.BEST: avg 0.00s, min 0.00s, max 0.00s
bubble, n=5000 - Case.BEST: avg 0.00s, min 0.00s, max 0.00s
bubble, n=10000 - Case.BEST: avg 0.00s, min 0.00s, max 0.00s

---

РЕДАКТИРОВАТЬ:

Я воспользовался советом @ asaf-rosemarin и попытался заменить цикл while на цикл for, чтобы увидеть,это сделает синхронизацию более равномерной, но это никак не повлияет на производительность

def insertion_sort(arr):
    for i in range(1, len(arr)):
        # n
        for j in range(i, 0, -1):
            # worst case n, best case 1
            if arr[j - 1] > arr[j]:
                scratch = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = scratch
            else:
                break
    return arr

output:

timing insertion sort...
insertion, n=1000 - Case.AVERAGE: avg 0.03s, min 0.03s, max 0.03s
insertion, n=5000 - Case.AVERAGE: avg 0.72s, min 0.03s, max 0.74s
insertion, n=10000 - Case.AVERAGE: avg 3.61s, min 0.03s, max 3.13s
timing selection sort...
selection, n=1000 - Case.AVERAGE: avg 0.02s, min 0.02s, max 0.02s
selection, n=5000 - Case.AVERAGE: avg 0.47s, min 0.02s, max 0.51s
selection, n=10000 - Case.AVERAGE: avg 2.52s, min 0.02s, max 2.17s
timing bubble sort...
bubble, n=1000 - Case.AVERAGE: avg 0.10s, min 0.09s, max 0.10s
bubble, n=5000 - Case.AVERAGE: avg 2.56s, min 0.09s, max 2.50s
bubble, n=10000 - Case.AVERAGE: avg 12.31s, min 0.09s, max 10.34s

Answer 1

У меня есть идея.

В сортировке вставки во внутреннем цикле вы заменяете элементы в массиве каждым циклом.Это создает алгоритм псевдопузырьковой сортировки в том, что касается реализации (количество операций чтения-записи).Возможно, вы можете удерживать следующий номер в позиции i в переменной, найти подходящее место в вашем отсортированном массиве, а затем переместить все элементы.

Кроме того, по сравнению с сортировкой выбора количество обращений к массиву намного выше.В сортировке выбора вы делаете только 2 обращения к массиву во внутреннем цикле, и индексы не изменяются, если не существует нового минимального числа, поэтому Python кэширует его.В сортировке вставкой вы делаете 6 обращений к массиву во внутреннем цикле, ваш индекс изменяется с каждой итерацией, и все ваши обращения к массиву зависят от переменной index, поэтому python не может ее кешировать.Когда вы добавляете вышеупомянутые операции чтения-записи, он становится медленнее.

Answer 2

Реализация вставной сортировки, хотя и технически правильная, является неоптимальной.

• Она выполняет 3 назначения, а
• Она проверяет два условия (index > 0 и arr[index - 1] > arr[index])

на каждой итерации внутреннего цикла.Вы можете уйти с одного задания и одного теста.Чтобы удалить ненужные назначения, рассмотрите

def insertion_sort(arr):
    for i in range(1, len(arr)):
        index = i
        scratch = arr[i]
        while index > 0 and arr[index - 1] > arr[index]:
            arr[index] = arr[index - 1]
            index -= 1
        arr[index] = scratch
    return arr

Чтобы уменьшить количество тестов, рассмотрите

def insertion_sort(arr):
    for i in range(1, len(arr)):
        scratch = arr[i]
        if scratch < arr[0]:
            # Don't bother about the values; just shift the array
            for index in range(i, 0, -1):
                arr[index] = arr[index - 1]
            arr[0] = scratch
        else:
            index = i
            # Don't bother about indices: the loop is naturally guarded by arr[0]
            while arr[index - 1] > arr[index]:
                arr[index] = arr[index - 1]
                index -= 1
            arr[index] = scratch
    return arr

---

Есть немного проблем с синхронизацией алгоритмов.

Во-первых, для правильного сравнения вы должны сравнить их с теми же данными.При хронировании среднего случая каждый алгоритм получает свои собственные наборы перемешанных массивов.

Во-вторых, total накапливается по сериям разных размеров.Это дает несправедливое преимущество алгоритму, который работает лучше на более коротких наборах данных.

---

Nitpick: питонический способ обмена arr[i] с arr[min_index] (выборочная сортировка) равен

    arr[i], arr[min_index] = arr[min_index], arr[i]

Answer 3

Вы правильно понимаете сложность времени, и я не смог найти ошибок в ваших реализациях, поэтому я предполагаю, что причина в том, что for ... in range быстрее, чем while цикл в python.
(Больше информации здесь Почему цикл по диапазону () в Python быстрее, чем при использовании цикла while? )

Редактировать:

Причина такого несоответствия между сравнением времениСложности и сравнение фактического времени выполнения реализаций заключается в том, что сложность времени касается только количества сравнений, игнорируя при этом дополнительные операции (например, O(1) для каждого сравнения), но эти дополнительные операции и способ их реализации (например,скомпилированный или интерпретированный, удобство кэша) может значительно повлиять на время выполнения.