To sort a circular array, we need to:
- Find the smallest element that is not in its correct position and swap it with the element that should be there.
- Compute the solution as the sum of the distances between the original and final positions of all the swapped elements.
- Use a simple but slow way to do this by checking each element with its next and previous elements, which would take time. This means that for an array of size , we would need to make comparisons, which grows very fast as increases. This is not efficient enough.
- Use a faster way to do this by using another array to store the index of each element, compute the distance between the current and the desired positions, and update the index after each swap. This would take time. This means that for an array of size , we would only need to make comparisons, which grows much slower as N increases.
- Take into account the circularity of the array, which allows us to swap elements in either direction: clockwise or anticlockwise. We should choose the direction that minimizes the distance.