AlgoDesign

Almost sorted

1def almostSorted(nums):
2  def isSorted(arr, left, right):
3    i = left + 1
4    while i <= right:
5      if arr[i - 1] > arr[i]: return False
6      i += 1
7    return True
8  
9  if isSorted(nums, 0, len(nums) - 1): print("yes")
10  else:
11    sortedNums = list(nums)
12    sortedNums.sort()
13    
14    # find first left index's element which is not equal to sortedNums
15    l = 0
16    while l < len(nums) and nums[l] == sortedNums[l]: l += 1
17    
18    # find first right index's element which is not equal to sortedNums
19    r = len(nums) - 1
20    while r >= 0 and nums[r] == sortedNums[r]: r -= 1
21    
22    # check if exchanging l, r makes it sorted
23    nums[l], nums[r] = nums[r], nums[l]
24    if isSorted(nums, 0, len(nums) - 1): print("yes\nswap {i} {j}".format(i=l + 1, j=r + 1))
25    else:
26      nums[l], nums[r] = nums[r], nums[l]
27      seg = list(nums[l:r + 1])
28      seg.reverse()
29      if isSorted(seg, 0, len(seg) - 1): print("yes\nreverse {i} {j}".format(i=l + 1, j=r + 1))
30      else: print("no")