I am trying to set up cyclic sort, where the range of numbers are known ahead of time
def cyclic_sort(nums):
# TODO: Write your code here
i = 0
while i < len(nums):
while nums[i] - 1 != i:
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
i += 1
return nums
print(cyclic_sort([2, 1, 3]))
However the code just hangs however when I refactor to the below the code runs
def cyclic_sort(nums):
# TODO: Write your code here
i = 0
while i < len(nums):
while nums[i] - 1 != i:
other = nums[i] - 1
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
i += 1
return nums
print(cyclic_sort([2, 1, 3]))
Can someone help me understand what is happening?
nums[i] gets reassigned first, so when nums[nums[i] - 1] = ... is evaluated, it is taking the new value of nums[i], which in this case is 1.
So you get nums[0] = 1, and then nums[1-1] = 2, in your example.
You are setting the value of the current element to the new value you want to swap with, and then setting the element at the position of the value of the swapped element to the current value.
Your code is equivalent to:
x, y = nums[nums[i] - 1], nums[i]
nums[i] = x #nums[i] is set to value of element you want to swap
nums[nums[i] - 1] = y #nums[(value at swapped element) - 1] = (current elements original value)
You also don't need the while loop, which doesn't do anything useful, because you already know which position the number should be in based on the value, so you only need to check it once per position.
Swap order of assignments, since nums[i] doesn't get affected by changing the value of nums[nums[i] - 1].
def cyclic_sort(nums):
# TODO: Write your code here
i = 0
while i < len(nums):
if nums[i] - 1 != i:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
i += 1
return nums
print(cyclic_sort([2, 1, 3]))