счетчики слияния, кучи и быстрой сортировки не отображаются должным образом

Question

import random, timeit

#Qucik sort
def quick_sort(A,first,last):
    global Qs,Qc
    if first>=last: return
    left, right= first+1, last
    pivot = A[first]
    while left <= right:
        while left <=last and A[left]<pivot:
            Qc= Qc+1
            left= left + 1
        while right > first and A[right] >= pivot:
            Qc=Qc+1
            right = right -1
        if left <= right:   
            A[left],A[right]=A[right],A[left]
            Qs = Qs+1
            left= left +1
            right= right-1

    A[first],A[right]=A[right],A[first]
    Qs=Qs+1
    quick_sort(A,first,right-1)
    quick_sort(A,right+1,last)


#Merge sort
def merge_sort(A, first, last): # merge sort A[first] ~ A[last]
    global Ms,Mc
    if first >= last: return
    middle = (first+last)//2
    merge_sort(A, first, middle)
    merge_sort(A, middle+1, last)
    B = []
    i = first
    j = middle+1
    while i <= middle and j <= last:
        Mc=Mc+1
        if A[i] <= A[j]:
            B.append(A[i])
            i += 1
        else:
            B.append(A[j])
            j += 1
    for i in range(i, middle+1): 
        B.append(A[i])
        Ms=Ms+1
    for j in range(j, last+1):
        B.append(A[j])
    for k in range(first, last+1): A[k] = B[k-first]

#Heap sort
def heap_sort(A):
    global Hs, Hc
    n = len(A)
    for i in range(n - 1, -1, -1):
        while 2 * i + 1 < n:
            left, right = 2 * i + 1, 2 * i + 2
            if left < n and A[left] > A[i]:
                m = left
                Hc += 1
            else:
                m = i
                Hc += 1
            if right < n and A[right] > A[m]:
                m = right
                Hc += 1
            if m != i:
                A[i], A[m] = A[m], A[i]
                i = m
                Hs += 1
            else:
                break                               
    for i in range(n - 1, -1, -1):
        A[0], A[i] = A[i], A[0]
        n -= 1
        k = 0
        while 2 * k + 1 < n:
            left, right = 2 * k + 1, 2 * k + 2
            if left < n and A[left] > A[k]:
                m = left
                Hc += 1
            else:
                m = k
                Hc += 1
            if right < n and A[right] > A[m]:
                m = right
                Hc += 1
            if m != k:
                A[k], A[m] = A[m], A[k]
                k = m
                Hs += 1
            else:
                break

#

def check_sorted(A):
    for i in range(n-1):
        if A[i] > A[i+1]: return False
    return True

#

#

Qc, Qs, Mc, Ms, Hc, Hs = 0, 0, 0, 0, 0, 0

n = int(input())
random.seed()
A = []
for i in range(n):
    A.append(random.randint(-1000,1000))
B = A[:]
C = A[:]

print("")
print("Quick sort:")
print("time =", timeit.timeit("quick_sort(A, 0, n-1)", globals=globals(), number=1))
print("  comparisons = {:10d}, swaps = {:10d}\n".format(Qc, Qs))
print("Merge sort:")
print("time =", timeit.timeit("merge_sort(B, 0, n-1)", globals=globals(), number=1))
print("  comparisons = {:10d}, swaps = {:10d}\n".format(Mc, Ms))

print("Heap sort:")
print("time =", timeit.timeit("heap_sort(C)", globals=globals(), number=1))
print("  comparisons = {:10d}, swaps = {:10d}\n".format(Hc, Hs))


assert(check_sorted(A))
assert(check_sorted(B))
assert(check_sorted(C))

Я сделал код, который говорит, сколько времени занимает сортировка списка размером n (ввод числа) с 3 способами сортировки. Однако я обнаружил, что мой результат довольно неожиданный.

Quick sort:
time = 0.0001289689971599728
  comparisons =        474, swaps =        168

Merge sort:
time = 0.00027709499408956617
  comparisons =        541, swaps =         80

Heap sort:
time = 0.0002578190033091232
  comparisons =        744, swaps =        478

Quick sort:
time = 1.1767549149953993
  comparisons =    3489112, swaps =     352047

Merge sort:
time = 0.9040642600011779
  comparisons =    1536584, swaps =      77011

Heap sort:
time = 1.665754442990874
  comparisons =    2227949, swaps =    1474542

Quick sort:
time = 4.749891302999458
  comparisons =   11884246, swaps =     709221

Merge sort:
time = 3.1966246420051903
  comparisons =    3272492, swaps =     154723

Heap sort:
time = 6.2041203819972
  comparisons =    4754829, swaps =    3148479

Как видите, мои результаты сильно отличаются от того, что я узнал. Подскажите, пожалуйста, почему быстрая сортировка не самая быстрая в моем коде? и почему слияние является самым быстрым.

Answer 1

Я вижу, что вы выбираете первый элемент массива в качестве стержня в быстрой сортировке. Теперь рассмотрим порядок элементов несортированного массива. Это случайно? Как вы генерируете входной массив?

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

Для оптимальной производительности быстрой сортировки O (n log n) ваша точка должна быть как можно ближе к срединному значению. Чтобы увеличить вероятность того, что дело обстоит именно так, подумайте о том, чтобы изначально выбрать 3 значения случайным образом из массива и использовать медианное значение в качестве точки поворота. Очевидно, что чем больше значений вы выбираете медиану изначально, тем выше вероятность того, что ваш пивот более эффективен, но вы добавляете дополнительные движения, выбирая эти значения для начала, так что это компромисс. Я полагаю, что можно было бы даже точно рассчитать, сколько элементов должно быть выбрано по отношению к размеру массива для оптимальной производительности.

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

TL: DR я предполагаю, что первый элемент входного массива очень близок к тому, чтобы быть наименьшим или наибольшим значением этого массива, и он в конечном итоге является стержнем вашего алгоритма быстрой сортировки.