## Interview Question

**Country:**United States

**Interview Type:**Phone Interview

One more problem is that if it's an array then the rotation itself will require shift hence will be more costly. I think 'havefun''s solution is better. requires O(n) op.

Just think for it using disjoint cycles of the given permutation

For example if N = 5, and given a permutation (3, 4, 1, 5, 2) and want to sort it

Then you have 2 disjoint cycles in this permutation

1st: 3 --> 1 --> 3

2nd: 4 --> 5 --> 2 --> 4

(generate these cycles using the index of every number, 3 will point to the 3rd place in the permutation which is 1 and 1 will show to the 1st place which is 3)

Then given these disjoint cycles, just rotate them till they are all adjusted.

//given an array of size n, it holds distinct integers from 1 to n. Give an algorithm to sort the array? one way is to just assign a[i]=i in the array. how to sort the array using the elements of the array and not just assigning directly

```
public class Sort {
public static void main(String[] args) {
int[] arr = { 2, 4, 1, 3 };
int i = 0;
int j = 0;
while (j < arr.length-1) {
i=j;
int x=i+1;
while (arr[i] != i+1) {
swap(arr, i, x);
x++;
}
j++;
}
for(int a: arr)
{
System.out.print(a + ", ");
}
}
private static void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
}
```

The time complexity is O(n^2), no additional space is required - O(n) - the size of the array itself

The following pseudo code solve it in O(n) time:

- havefun January 04, 2013index = 1

While (index <= N){

swap(a[index],a[a[index]]);

while(a[index] == index)

index++;

}