У меня задание реализовать сортировку Шелла используя эмпирическую последовательность Марцина Циура. Оно сделано. Но есть одна проблема, когда я считаю количество перестановок то оно выдает всегда одинаковые числа для разного размера массива. Например есть массив рандомный размером N
и такого же размера только статический и упорядоченный, то программа выдает кол-во перестановок для обоих массивов одинаковую, хотя кол-во сравнений разное ведь к примеру массив упорядоченный он уже есть отсортированный, а это значит что престановок должно быть 0
. Как решить проблему с подсчетом перестановок?
Собственно вот мой код(я брал только одну размерность что бы не было много кода)
from time import clock
from random import randint
LIST_SIZE1 = 10
LIST_SIZE2 = 100
LIST_SIZE3 = 1000
LIST_SIZE4 = 5000
LIST_SIZE5 = 200
LIST_SIZE6 = 300
LIST_SIZE7 = 400
def time_fn(to_call,param):
start = clock()
result = to_call(param)
d_time = clock()-start;
return d_time,result
def areEqual(a,b):
return True if a==b else False
def run_test(to_test,test_with):
time,value = time_fn(to_test,test_with)
return [time,"OK"] if value==t_sorted else [time,"FAIL"]
def shell_sort(to_sort):
gaps = [701,301,132,57,23,10,4,1]
for gap in gaps:
count_compariont = 0
count = 0
i = gap
while i <= len(to_sort)-1:
hole = to_sort[i]
j = i
count += 1
while j>=gap and to_sort[j-gap] > hole:
to_sort[j] = to_sort[j-gap]
j-=gap
count_compariont += 1
to_sort[j] = hole
i+=gap
print("Counter of permutations ", count)
print("Counter of comparison ", count_compariont)
return to_sort
"""Output"""
print("Testing ", " sorting algorithm with a ", LIST_SIZE4, " element list...")
print("Generating and sorting test values...")
test = [randint(-100,100) for i in range(LIST_SIZE4)]
t_sorted = shell_sort(test)
sorting4 = t_sorted
print("RUNNING TESTS...")
print("Shell sort: ", run_test(shell_sort,test))
print("\n")
print("Array constant ")
print("Testing ", " sorting algorithm with a ", LIST_SIZE4, " element list...")
print("Generating and sorting test values...")
test1 = []
test1 = [i for i in range(LIST_SIZE4)]
t_sorted = shell_sort(test1)
#print("SSSSSSSSS ", t_sorted)
sorting1 = t_sorted
#The tests
print("RUNNING TESTS...")
print("Shell sort: ", run_test(shell_sort,test1))
print("\n")
А вот результат
Testing sorting algorithm with a 5000 element list...
Generating and sorting test values...
Counter of permutations 4999
Counter of comparison 4480801
RUNNING TESTS...
Counter of permutations 4999
Counter of comparison 0
Shell sort: [0.005307999999999868, 'OK']
Array constant
Testing sorting algorithm with a 5000 element list...
Generating and sorting test values...
Counter of permutations 4999
Counter of comparison 0
RUNNING TESTS...
Counter of permutations 4999
Counter of comparison 0
Shell sort: [0.005185999999999691, 'OK']