Я сделал два исходных кода алгоритма сортировки вставками.
def insertsort(iterable) :
for current in range(len(iterable)) : # 'current' is the index of the element being sorted
compare, n = 0,0 # Initializes 'compare' and 'n' which is used in for-loop in each current for-loop
current_value = iterable[current] # Saves the element being sorted since the corresponding space will be assigned by the leading value
for compare in range(0,current) : # Compares the element from [0] to the element right ahead of [current]
if iterable[compare] > iterable[current] : # Finds where to insert 'current_value,' stored value of [current]
for n in range(current,compare,-1) : # Translate the values to one space to make the space where 'current_value' will be put empty
iterable[n] = iterable[n-1]
iterable[compare] = current_value # Insert the saved value of [current] to the right place
return(iterable)
Первый - тот, который я сделал сам без всякого руководства.
def insertsort(iterable) :
for current in range(1,len(iterable)) : # iterable[0] is consdiered as resorted in the beginning
current_value = iterable[current] # saving current value
compare = current
while 0 < compare and iterable[compare-1] > current_value : # finding out where to put the sorted current value
iterable[compare] = iterable[compare-1] # this line in the while loop moves the elements not sorted
compare -= 1
iterable[compare] = current_value # put current value into the right place that the while loop found out
return(iterable)
Второй - это я
Сравнивая два, я обнаружил, что второй из целых rnet короче, чем тот, который я сделал.
Второй также продемонстрировал кажущуюся эффективную производительность в соответствии с среднее время выполнения за 10 раз, сортировка 10000 последовательных элементов (data = [i for i in range (10000, 0, -1)]
Это было примерно на 0,4 секунды быстрее, затрачивая около 16 секунд, чтобы отсортировать их все .
Однако при тестировании со 100 000 последовательных элементов (data = [i for i in range (100000, 0, -1)]) первый (который я сделал) был быстрее, чем второй.
Первый был около 1700 секунд, что на 200 секунд быстрее, чем второй.
Вот мой вопрос.
- Какова временная сложность каждый код? Я предполагаю, что оба n ^ 2, хотя я не конечно.
- Почему тот, который я сделал, кажется, показывает лучшие характеристики? Я сделал for-l oop и if-statement в while l oop во втором, но, я думаю, сделал его медленнее.
На всякий случай прилагаю метод измерения времени, которым пользовался. Я сослался на { ссылка }