Key idea :Swapping based
for example :{1,2,3,4} Rotate 2 left
{4,1,2,3} Rotate 1 left
{3,4,1,2} Rotate 0 left return..:)
O(nk) time, n is array length and k is number of rotation
----------------------
Improved method:Reverse-based
for example :{1,2,3,4} Rotate 2
Reverse {1,2} and {3,4} we get {2,1,4,3}
Reverse {2,1,4,3} we get {3,4,1,2}
O(n) time, n is array length
package array;
public class RotateArray {
int array[];
public RotateArray(int array[]) {
int i = 0;// for indexing array
System.out.print("Input Array : ");
this.array = new int[array.length];
for (int a : array) {
this.array[i++] = a;
}
printArray();
System.out.println();
}
void rotateKPosNaive(int k) {
for (int i = 0; i < k; i++)
rotatebyOne();
System.out.print("Rotated Array : ");
printArray();
System.out.println();
}
void rotateKPosAdv(int k) {
reverse(0, k - 1);
reverse(k, array.length - 1);
reverse(0, array.length - 1);
System.out.print("Rotated Array : ");
printArray();
}
void reverse(int start, int end) {
for (int i = start; i <= (start + end + 1) / 2; i++) {
// swap(i,end-i+start);//is used with i<=(start+end)/2
swap(i, end--);
}
}
void printArray() {
for (int a : array)
System.out.print(a);
}
void rotatebyOne() {
int temp = array[0];
for (int i = 1; i < array.length; i++) {
array[i - 1] = array[i];
}
array[array.length - 1] = temp;
}
void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int sample1[] = { 1, 2, 3, 4, 5, 6, 7 };
new RotateArray(sample1).rotateKPosNaive(3);
new RotateArray(sample1).rotateKPosAdv(3);
}
}
Output: Input Array : 1234567 Rotated Array : 4567123 Input Array : 1234567 Rotated Array : 4567123