Problem:
Design an algorithm that places the kth element of an array in position 1, the (k+1) th element in position 2 etc. The original 1st element is placed at (n-k+1) and so on.
Solution:
package array.programs;
import java.util.Scanner;
public class ShuffleTheArray {
static int number;
static int[] numberArray;
Scanner scanner;
static int shufflePosition;
public static void main(String[] args) {
ShuffleTheArray shuffleTheArray = new ShuffleTheArray();
shuffleTheArray.getTheNumbers();
System.out.println("before");
shuffleTheArray.printTheArray();
shuffleTheArray.shiftK2(numberArray, number, shufflePosition);
System.out.println("after");
shuffleTheArray.printTheArray();
}
public void getTheNumbers(){
scanner = new Scanner(System.in);
System.out.println("enter how many numbers");
number = scanner.nextInt();
numberArray = new int[number];
initializeTheNumbers();
System.out.println("enter from which element of an array want to starts");
shufflePosition = scanner.nextInt();
scanner.close();
}
public void initializeTheNumbers(){
for(int i = 0; i < number; i++){
System.out.println("enter the number");
numberArray[i] = scanner.nextInt();
}
}
public void printTheArray(){
for(int i = 0; i< number; i++){
System.out.print(numberArray[i] + " ");
}
}
public void shuffleTheArray(){
int temp = 0;
for (int i = 0; i < numberArray.length; i++) {
temp = numberArray[i];
numberArray[i] = numberArray[shufflePosition-1- i];
numberArray[number-shufflePosition] = temp;
shufflePosition++;
}
}
void shiftK2(int []arr, int size, int k)
{
//kth elemen to 1st element, k+1th to 2nd...and so on... Dromey Pg. 143. Exercise 4.1.3
//Method 2. Calculate GCD of n, k then shift blocks. Refer http://www.geeksforgeeks.org/array-rotation/ for images.
int i = size, j = k;
while(i != j)
{
if(i > j)
i = i-j;
else
j = j-i;
}
i=i-1;
for(; i>=0; i--)
{
int temp = arr[i];
int p;
j = i;
while(true)
{
p = j+k;
p = p%size;
arr[j] = arr[p];
j = p;
if((j+k)%size == i)
{
arr[j] = temp;
break;
}
}
}
}
}
Output:
enter how many numbers
7
enter the number
1
enter the number
2
enter the number
3
enter the number
4
enter the number
5
enter the number
6
enter the number
7
enter from which element of an array want to starts
3
before
1 2 3 4 5 6 7 after
4 5 6 7 1 2 3
Design an algorithm that places the kth element of an array in position 1, the (k+1) th element in position 2 etc. The original 1st element is placed at (n-k+1) and so on.
Solution:
package array.programs;
import java.util.Scanner;
public class ShuffleTheArray {
static int number;
static int[] numberArray;
Scanner scanner;
static int shufflePosition;
public static void main(String[] args) {
ShuffleTheArray shuffleTheArray = new ShuffleTheArray();
shuffleTheArray.getTheNumbers();
System.out.println("before");
shuffleTheArray.printTheArray();
shuffleTheArray.shiftK2(numberArray, number, shufflePosition);
System.out.println("after");
shuffleTheArray.printTheArray();
}
public void getTheNumbers(){
scanner = new Scanner(System.in);
System.out.println("enter how many numbers");
number = scanner.nextInt();
numberArray = new int[number];
initializeTheNumbers();
System.out.println("enter from which element of an array want to starts");
shufflePosition = scanner.nextInt();
scanner.close();
}
public void initializeTheNumbers(){
for(int i = 0; i < number; i++){
System.out.println("enter the number");
numberArray[i] = scanner.nextInt();
}
}
public void printTheArray(){
for(int i = 0; i< number; i++){
System.out.print(numberArray[i] + " ");
}
}
public void shuffleTheArray(){
int temp = 0;
for (int i = 0; i < numberArray.length; i++) {
temp = numberArray[i];
numberArray[i] = numberArray[shufflePosition-1- i];
numberArray[number-shufflePosition] = temp;
shufflePosition++;
}
}
void shiftK2(int []arr, int size, int k)
{
//kth elemen to 1st element, k+1th to 2nd...and so on... Dromey Pg. 143. Exercise 4.1.3
//Method 2. Calculate GCD of n, k then shift blocks. Refer http://www.geeksforgeeks.org/array-rotation/ for images.
int i = size, j = k;
while(i != j)
{
if(i > j)
i = i-j;
else
j = j-i;
}
i=i-1;
for(; i>=0; i--)
{
int temp = arr[i];
int p;
j = i;
while(true)
{
p = j+k;
p = p%size;
arr[j] = arr[p];
j = p;
if((j+k)%size == i)
{
arr[j] = temp;
break;
}
}
}
}
}
Output:
enter how many numbers
7
enter the number
1
enter the number
2
enter the number
3
enter the number
4
enter the number
5
enter the number
6
enter the number
7
enter from which element of an array want to starts
3
before
1 2 3 4 5 6 7 after
4 5 6 7 1 2 3
No comments:
Post a Comment