small medium large xlarge

# PracProg2searchsort

1.

While loop version:

```def linear_search(lst, value):
""" (list, object) -> int

Return the index of the last occurrence of value in lst, or return
-1 if value is not in lst.

>>> linear_search([2, 5, 1, -3], 5)
1
>>> linear_search([2, 4, 2], 2)
2
>>> linear_search([2, 5, 1, -3], 4)
-1
>>> linear_search([], 5)
-1
"""

i = len(lst) - 1  # The index of the next item in lst to examine.

# Keep going until we reach the end of lst or until we find value.
while i != -1 and lst[i] != value:
i = i - 1

# If we fell off the end of the list, we didn't find value.
if i == -1:
return -1
else:
return i
```

For loop version:

```def linear_search(lst, value):
""" (list, object) -> int

Return the index of the last occurrence of value in lst, or return
-1 if value is not in lst.

>>> linear_search([2, 5, 1, -3], 5)
1
>>> linear_search([2, 4, 2], 2)
2
>>> linear_search([2, 5, 1, -3], 4)
-1
>>> linear_search([], 5)
-1
"""

# The first index is included, the second is not, and the third is the
# increment.
for i in range(len(lst) - 1, -1, -1):
if lst[i] == value:
return i

return -1
```

Sentinal version:

```def linear_search(lst, value):
""" (list, object) -> int

Return the index of the last occurrence of value in lst, or return
-1 if value is not in lst.

>>> linear_search([2, 5, 1, -3], 5)
1
>>> linear_search([2, 4, 2], 2)
2
>>> linear_search([2, 5, 1, -3], 4)
-1
>>> linear_search([], 5)
-1
"""

# Add the sentinel at the beginning.
lst.insert(0, value)

i = len(lst) - 1

# Keep going until we find value.
while lst[i] != value:
i = i - 1

# Remove the sentinel.
lst.pop(0)

# If we reached the beginning of the list we didn't find value.
if i == 0:
return -1
else:
# When we inserted, we shifted everything one to the right. Subtract 1
# to account for that.
return i - 1
```

2.

If there are duplicates, the one at the highest index is found.

3.

The question asks roughly how many times we need to search in order to make sorting the list first (on the order of N log_2 N steps) and then using binary search (on the order of log_2 N steps) faster than than just using linear search (on the order of N steps).

If there are k searches, then using linear search takes on the order of k * N steps.

It takes N log_2 N steps to sort a list with N items. In addition to the sorting time, there are all the binary searches to account for, each taking log_2 N steps, so this approach takes on the order of N log_2 N + k * N log_2 N steps.

```N log_2 N + k * log_2 N < k * N
[subtract k * log_2 N from both sides]
N log_2 N < k * N -  k * log_2 N
[simplify]
N log_2 N < k * (N - log_2 N)
[divide both sides by (N - log_2 N)]
(N log_2 N) / (N - log_2 N) < k
[N is much larger than log_2 N, so we simplify the denominator and multiply the numerator by 2
(remember, we want a rough answer)]
(2 * N log_2 N) / N < k
[simplify]
2 * log_2 N < k
```
The actual threshold is slightly smaller, but this is a fine rough estimate.

4.

a. Selection sort:

```[6, 5, 4, 3, 7, 1, 2]
[1, 5, 4, 3, 7, 6, 2]
[1, 2, 4, 3, 7, 6, 5]
[1, 2, 3, 4, 7, 6, 5]
[1, 2, 3, 4, 5, 6, 7]
# Because selection sort doesn't stop even though the list is sorted,
# there is one more iteration.
[1, 2, 3, 4, 5, 6, 7]
```

b. Insertion sort:

```[6, 5, 4, 3, 7, 1, 2]
[5, 6, 4, 3, 7, 1, 2]
[4, 5, 6, 3, 7, 1, 2]
[3, 4, 5, 6, 7, 1, 2]
[3, 4, 5, 6, 7, 1, 2]  # The 7 doesn't move on this iteration.
[1, 3, 4, 5, 6, 7, 2]
[1, 2, 3, 4, 5, 6, 7]
```
Page History
• V17: Paul Gries [almost 3 years ago]
• V16: Paul Gries [almost 3 years ago]
• V15: Paul Gries [almost 3 years ago]
• V14: Paul Gries [almost 3 years ago]
• V13: Paul Gries [almost 3 years ago]
• V12: Paul Gries [almost 3 years ago]
• V11: Paul Gries [almost 3 years ago]
• V10: Paul Gries [almost 3 years ago]
• V7: Paul Gries [almost 3 years ago]
• V9: System [almost 3 years ago]