01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
def min1 (lst):
  minSoFar = lst[0]
  for x in lst:
    if x < minSoFar:
      minSoFar = x
  return minSoFar

def min2 (lst):
  for x in lst:
    numSmaller = sum(y < x for y in lst)
    if numSmaller == 0:
       return x

import time
for f in [min1, min2]:
  print ("testing " + f.__name__)
  assert 1 == (min2 ([1, 12, 23, 3, 24, 25, 2]))
  assert 2 == (min2 ([12, 23, 3, 24, 25, 2]))
  assert 3 == (min2 ([12, 23, 3, 24, 25, 4]))
  assert 3 == (min2 ([12, 3, 24, 25]))
  base = 2000
  for multiplier in [1, 2, 4]:
    length = base * multiplier
    lst = [i for i in range(length)]        
    start = time.time()
    result = f (lst)
    end = time.time()
    print ("Duration of " + f.__name__ + "(" + str(len(lst)) + "): " + str(end - start))

def minPos1 (lst):
  minPosSoFar = 0
  for i in range(len(lst)):
    if lst[i] < lst[minPosSoFar]:
      minPosSoFar = i
  return minPosSoFar

assert 0 == (minPos1 ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPos1 ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPos1 ([12, 23, 3, 24, 25]))
assert 1 == (minPos1 ([12, 3, 24, 25]))

def minPos2 (lst):
  minSoFar = lst[0]
  minPosSoFar = 0
  for i in range(len(lst)):
    if lst[i] < minSoFar:
      minPosSoFar = i
      minSoFar = lst[i]
  return minPosSoFar

assert 0 == (minPos2 ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPos2 ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPos2 ([12, 23, 3, 24, 25]))
assert 1 == (minPos2 ([12, 3, 24, 25]))

def minPos3 (lst):
  minPosSoFar = 0
  n = len(lst)
  i = 1
  while i < n:
    if lst[i] < lst[minPosSoFar]:
      minPosSoFar = i
    i += 1
  return minPosSoFar

assert 0 == (minPos3 ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPos3 ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPos3 ([12, 23, 3, 24, 25]))
assert 1 == (minPos3 ([12, 3, 24, 25]))

def minPosR (lst):
  return minPosHelper (lst, 1, 0)

def minPosHelper (lst, i, minPosSoFar):
  if i >= len(lst):
    return minPosSoFar
  if lst[i] < lst[minPosSoFar]:
    return minPosHelper (lst, i + 1, i)
  else:
    return minPosHelper (lst, i + 1, minPosSoFar)

assert 0 == (minPosR ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPosR ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPosR ([12, 23, 3, 24, 25]))
assert 1 == (minPosR ([12, 3, 24, 25]))

print ("Finished tests")