1

У меня задание реализовать сортировку Шелла используя эмпирическую последовательность Марцина Циура. Оно сделано. Но есть одна проблема, когда я считаю количество перестановок то оно выдает всегда одинаковые числа для разного размера массива. Например есть массив рандомный размером 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']

1 ответ 1

1

Оба счетчика обнуляются на каждом новом значении gap, т.е. финальный вывод относится только к проходу с gap=1

Поэтому немудрено, что для Len=5000 выводится Counter of permutations 4999.

Да и считает этот счетчик вовсе не какие-то "permutations", а проходы по гребенке в массиве.

Вот счетчик с не менее загадочным названием count_compariont подсчитывает полуобмены (сдвиги элемента к финальной позиции)

4
  • а как мне тогда подсчитывать количество проходов?
    – Lado
    1 апр 2018 в 16:30
  • Обнуление счетчиков вынести перед for. Количество проходов не зависит от данных, только от размера массива и выбранной последовательности шагов. Вот количество обменов будет варьироваться - оно так и есть: 4480801 и 0
    – MBo
    1 апр 2018 в 16:35
  • а количество сравнений будет таким же как и количество обменов?
    – Lado
    1 апр 2018 в 17:39
  • нет, больше - не все сравнения вызывают обмены
    – MBo
    1 апр 2018 в 17:44

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.