CMU Coding Bootcamp
thecoded.prof
1from typing import Sequence, Literal, Set, Tuple
2from copy import deepcopy
3
4
5def isNearlySorted(L: Sequence[float]) -> Literal[False] | Sequence[float]:
6 """Returns a tuple of indices that need to be swapped to sort the list, or False if it cannot be sorted with a single swap."""
7 if not len(L):
8 return False
9 sortPath: Set[Tuple[int, int]] = set()
10 sortedList = list(deepcopy(L))
11 for i in range(len(L) - 1):
12 for j in range(len(L) - 1, i, -1):
13 a = sortedList[i]
14 b = sortedList[j]
15 if a > b:
16 sortedList[i], sortedList[j] = b, a
17 sortPath.add((i, j))
18 if len(sortPath) > 1:
19 return False
20 if len(sortPath) == 1:
21 return list(sortPath.pop())
22 return False
23
24
25print("Testing isNearlySorted()...", end="")
26assert isNearlySorted([2, 7, 5, 4]) == [1, 3]
27assert isNearlySorted([2, 3, 1]) == False
28assert isNearlySorted([1, 2, 3]) == False
29assert isNearlySorted([-1, 1, 0, 5]) == [1, 2]
30assert isNearlySorted([5, 6, 9, 8, 8]) == [2, 4]
31assert isNearlySorted([2, 1]) == [0, 1]
32assert isNearlySorted([3, 3]) == False
33assert isNearlySorted([2]) == False
34assert isNearlySorted([]) == False
35
36# Verify that the function is non-mutating
37L = [2, 7, 5, 4]
38isNearlySorted(L)
39assert L == [2, 7, 5, 4]
40print("Passed!")