Exchange sort is similar to selection sort, just swaps "overly eagerly" instead of finding the minimum and doing only one swap. And the swaps affect how often the if ...
is true. For example for 8000 random numbers, in exchange sort it's true ~270 times more often:
trues in trues in
n exchangeSort selectionSort ratio
----------------------------------------
1000 244828 5368 45.6
2000 1002555 12341 81.2
4000 4017151 27691 145.1
8000 16359262 60394 270.9
Why is it so much more often? Does someone have a good explanation? I did expect some noticeable difference, but not this much.
What's the expected number of trues for each?. For exchange sort it looks quadratic, for selection sort maybe linearithmic?
Code (Try it online!):
def exchangeSort(nums):
trues = 0
for i in range(len(nums)-1):
for j in range(i + 1, len(nums)):
if nums[j] < nums[i]:
trues += 1
nums[j], nums[i] = nums[i], nums[j]
return trues
def selectionSort(nums):
trues = 0
for i in range(len(nums)-1):
idx_min = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[idx_min]:
trues += 1
idx_min = j
nums[idx_min], nums[i] = nums[i], nums[idx_min]
return trues
from random import random
print(' trues in trues in')
print(' n exchangeSort selectionSort ratio')
print('----------------------------------------')
for n in 1000, 2000, 4000, 8000:
nums = [random() for _ in range(n)]
trues1 = exchangeSort(nums.copy())
trues2 = selectionSort(nums.copy())
print(f'{n} {trues1:10} {trues2:10} {trues1/trues2:10.1f}')
This was inspired by another question, from which I also took the code.