为什么我要多计算这个插入排序算法中的比较次数?
Why am I over counting the amount of comparisons in this insertion sort algorithm?
我正在尝试计算插入排序中的比较次数。目前我的比较计数测量值超出了应有的值,我不确定为什么。
def compare(data, a, b):
"""Returns True if element at index a > element at index b"""
return data[a] > data[b]
def swap(data, a, b):
"""Swaps the element at index a with element at index b"""
data[a], data[b] = data[b], data[a]
def insertion_sort(data):
"""Sorts the list into ascending order"""
comparison_count = 0
swap_count = 0
for index in range(1, len(data)):
position = index
while position > 0 and compare(data, position - 1, position):
comparison_count += 1
swap(data, position - 1, position)
swap_count += 1
position -= 1
comparison_count += 1
print('Length:', len(data), 'Comparisons:', comparison_count, 'Swaps:', swap_count)
例如对列表进行排序
[50, 63, 11, 79, 22, 70, 65, 39, 97, 48]
将比较的数量多算一个。
如果 position > 0
不成立,则不会评估 compare(data, position - 1, position)
,但无论如何您都会跟进 comparison_count += 1
。
修复它并组合增量的直接方法(以整体更优雅的循环为代价)是:
while position > 0:
comparison_count += 1
if not compare(data, position - 1, position):
break
swap(data, position - 1, position)
swap_count += 1
position -= 1
也等同于
for index in range(1, len(data)):
for position in range(index, 0, -1):
comparison_count += 1
if not compare(data, position - 1, position):
break
swap_count += 1
swap(data, position - 1, position)
我正在尝试计算插入排序中的比较次数。目前我的比较计数测量值超出了应有的值,我不确定为什么。
def compare(data, a, b):
"""Returns True if element at index a > element at index b"""
return data[a] > data[b]
def swap(data, a, b):
"""Swaps the element at index a with element at index b"""
data[a], data[b] = data[b], data[a]
def insertion_sort(data):
"""Sorts the list into ascending order"""
comparison_count = 0
swap_count = 0
for index in range(1, len(data)):
position = index
while position > 0 and compare(data, position - 1, position):
comparison_count += 1
swap(data, position - 1, position)
swap_count += 1
position -= 1
comparison_count += 1
print('Length:', len(data), 'Comparisons:', comparison_count, 'Swaps:', swap_count)
例如对列表进行排序
[50, 63, 11, 79, 22, 70, 65, 39, 97, 48]
将比较的数量多算一个。
如果 position > 0
不成立,则不会评估 compare(data, position - 1, position)
,但无论如何您都会跟进 comparison_count += 1
。
修复它并组合增量的直接方法(以整体更优雅的循环为代价)是:
while position > 0:
comparison_count += 1
if not compare(data, position - 1, position):
break
swap(data, position - 1, position)
swap_count += 1
position -= 1
也等同于
for index in range(1, len(data)):
for position in range(index, 0, -1):
comparison_count += 1
if not compare(data, position - 1, position):
break
swap_count += 1
swap(data, position - 1, position)