Cyclic sort

Question 1

What is the definition of Cyclic Sort?

Answer 1

Sorts array by placing elements at their index (value-1).

Question 2

When is Cyclic Sort used?

Answer 2

Used for arrays with values 1 to n, missing/duplicates.

Question 3

What are the key steps in Cyclic Sort?

Answer 3

1. Iterate array, swap element to its correct index (value-1).
2. Continue until element is correct or visited.
3. Identify missing/duplicates post-sort.

Question 4

How does Cyclic Sort apply to Find Missing Number?

Answer 4

Find missing number in array of 0 to n by placing each value at index (value) and finding missing index.

Question 5

What is the time and space complexity of Cyclic Sort?

Answer 5

Time: O(n), Space: O(1).

Question 6

What are the gotchas in Cyclic Sort?

Answer 6

Out-of-range values, duplicates.

Question 7

Provide a code example for Find Missing Number.

Answer 7

```python
from typing import List
def find_missing_number(nums: List[int]) -> int:
i, n = 0, len(nums)
while i < n:
correct = nums[i]
if 0 <= correct < n and nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
for i in range(n):
if nums[i] != i:
return i
return n
~~~

Question 8

What is a visual representation for Cyclic Sort?

Answer 8

[Add image manually].