Wednesday 30 August 2017

Java Code to Partitioning an Array

Problem:

Given a randomly ordered array of n elements, partition the elements into two subsets such that elements <= x are in one subset and elements >x are in the other subset.

Solution:

package array.programs;

import java.util.Arrays;
import java.util.Scanner;

public class PartitioningAnArray {

int[] numbers;
int[] firstSetArray;
int[] secondSetArray;
int pivot;


public static void main(String[] args) {
PartitioningAnArray partitioningAnArray = new PartitioningAnArray();
partitioningAnArray.getTheNumbers();
partitioningAnArray.partitionArray();
System.out.println("the original Array is ");
partitioningAnArray.printTheArray(partitioningAnArray.numbers);
System.out.println("the first set Array is ");
partitioningAnArray.printTheArray(partitioningAnArray.firstSetArray);
System.out.println("the second set Array is ");
partitioningAnArray.printTheArray(partitioningAnArray.secondSetArray);
}

public void getTheNumbers(){
int n = 0;
Scanner scanner = new Scanner(System.in);
System.out.println("how many numbers");
n = scanner.nextInt();

numbers = new int[n];
firstSetArray = new int[n];
secondSetArray = new int[n];

for (int i = 0; i < numbers.length; i++) {
System.out.println("enter number");
numbers[i] = scanner.nextInt();
}
System.out.println("enter the number to act as pivot");
pivot = scanner.nextInt();
scanner.close();
}

public void partitionArray(){
Arrays.sort(numbers);
int j = 0;
int k = 0;
for (int i = 0; i < numbers.length; i++) {
if(numbers[i] <= pivot){
firstSetArray[j++] = numbers[i];
}
else if(numbers[i] > pivot){
secondSetArray[k++] = numbers[i];
}
}
}

public void printTheArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}


Output:

how many numbers
10
enter number
28
enter number
26
enter number
25
enter number
11
enter number
16
enter number
12
enter number
24
enter number
29
enter number
6
enter number
10
enter the number to act as pivot
16
the original Array is
6 10 11 12 16 24 25 26 28 29
the first set Array is
6 10 11 12 16 0 0 0 0 0
the second set Array is
24 25 26 28 29 0 0 0 0 0


No comments:

Post a Comment

Program for primality test in JAVA

Problem: ============= Program for primality test in JAVA What is primality test? A primality test is an algorithm for determining wh...