Какой массив из 10 ячеек будет сортироваться "Пузырьком" за меньшее количество перестановок, чем "быстрой сортировкой"?

Question

A=[4,1,8,9,3,7,2,10,6,5]
B=A
N=len(A)
k=0
def qSort ( A, nStart, nEnd ):
    x=0
    if nStart >= nEnd: return
    L = nStart; R = nEnd
    X = A[(L+R)//2]
    x=x+1
    while L <= R:
        while A[L] < X: L,x=L+1,x+1
        while A[R] > X: R,x=R-1,x+1
        if L <= R:
            A[L], A[R] = A[R], A[L]
            L += 1; R -= 1
            x=x+1
    qSort ( A, nStart, R )
    qSort ( A, L, nEnd )
    return x
N = len(A)
for i in range(N-1):
  for j in range(N-2, i-1 ,-1):
    if A[j+1] < A[j]: 
      A[j], A[j+1] = A[j+1], A[j]
      k=k+1
print('Количество перестановок "Пузырьком":',k)
print('Количество перестановок "Быстрой сортировкой":',qSort(B,0,N-1))

Answer 1

Простой эксперимент и здравая логика подсказывают, что это будут массивы, которые практически отсортированы, либо массивы малой длины. Для того, чтобы провести этот эксперимент, давайте будем генерировать массивы различной длины и для каждой последовательности запомним число перестановок. Все те, которые изначально отсортированы выбросим как тривиальный случай. Мы можем нагенерировать очень много таких последовательностей. В конце выберем только те из них, для которых справедливо "число перестановок bubble_sort < число перестановок q_sort":

import numpy as np

perms = []

for i in range(1000):
    n = np.random.randint(8, 100)  #  случайный размер массива
    A_ = np.random.randint(0, 1000, n).tolist()  #  массив
    if all(A_[i] <= A_[i+1] for i in range(len(A_)-1)):  #  проверяем, что массив не отсортирован (не тривиальный случай)
        continue

    A = A_[::]
    B = A[::]
    N = len(A)
    k = 0

    for i in range(N-1):
      for j in range(N-2, i-1 ,-1):
        if A[j+1] < A[j]:
          A[j], A[j+1] = A[j+1], A[j]
          k=k+1
    b = qSort(B,0,N-1)
    if b < k:
        continue
    perms.append((k, b, A_))

print(sorted(perms, key=lambda el: el[0] - el[1]))

Пример ответа:

[(7, 8, [434, 110, 109, 339, 487, 919, 846, 644]), (7, 7, [333, 282, 17, 71, 502, 390, 425, 535]), (9, 9, [9, 163, 754, 75, 390, 993, 545, 790, 681])]

Замечание. Ответы для случайных массивов длины более 10, я не нашёл (их можно найти для тривиальных или почти тривиальных случаев)

БЛОГ НА HUSL

Какой массив из 10 ячеек будет сортироваться "Пузырьком" за меньшее количество перестановок, чем "быстрой сортировкой"?

Ответы (1 шт):