Cyclic Sort
Given a list containing n objects. At creation, each object was assigned a unique number from 1 to n based on the order in which it was created.
Create a function that sorts objects in-place based on consecutive O (n) numbers. No extra data structures are needed. For the sake of simplicity, suppose you are passed a list of integers that contain only consecutive numbers. However, each number is actually an object.
Input: [3, 1, 5, 4, 2] Output: [1, 2, 3, 4, 5]
Input: [2, 6, 4, 3, 1, 5] Output: [1, 2, 3, 4, 5, 6]
Input: [1, 5, 6, 4, 3, 2] Output: [1, 2, 3, 4, 5, 6]
Solution As you know, the list contains numbers in the range 1-n. Take advantage of this fact to come up with an efficient way to sort numbers. All numbers are unique, so you can place each number in the correct position. That is, 1 is placed at index 0, 2 is placed at index 1, and so on.
To place a number (or object in general) in the correct index, you first need to find it. If you first find the number and put it in the right place, O (N ^ 2), this is unacceptable.
Instead, repeat the list with one number at a time, and if the current number is not in the correct index, replace it with the number in the correct index. In this way, it looks up all the numbers, puts them in the correct index, and sorts the entire list.
def cyclic_sort(nums):
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i] # swap
else:
i += 1
return nums
def main():
print(cyclic_sort([3, 1, 5, 4, 2]))
print(cyclic_sort([2, 6, 4, 3, 1, 5]))
print(cyclic_sort([1, 5, 6, 4, 3, 2]))
main()
Recommended Posts