Skip to content

Instantly share code, notes, and snippets.

@bee-san
Last active December 27, 2020 00:00
Show Gist options
  • Save bee-san/78a3c1ad204ba4c365e9c9d00716a3fb to your computer and use it in GitHub Desktop.
Save bee-san/78a3c1ad204ba4c365e9c9d00716a3fb to your computer and use it in GitHub Desktop.
3 * n/2 - 2 comparisons, tournament method
x = [1, 5, 3, 9, 10, 6, 0, 11, 21, -10, 5]
small, large = x[0], x[0]
for i in range(1, len(x) - 1):
if x[i] < x[i + 1]:
small = min(x[i], small)
large = max(x[i + 1], large)
print(small, large)
# 3 * n/2 - 2 comparisons, tournament method
"""
If odd, set both to same value like above.
If even, perform one manual comparison to determine the min and max at the start.
if n is odd, we do 3[n/2] comparisons.
if n is even, we perform 1 initial comparison followed by 3(n - 2)/2 for a total of 3n(2 - 2).
The total compairsons at most is 3[n/2]
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment