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++;
}