(a) Given a binary array, implement in Java an algorithm to sort it in linear ru

Question

(a) Given a binary array, implement in Java an algorithm to sort it in linear running time complexity and constant space complexity.

Example:

Input: [1,0,1,0,0,0,1,0,1,0,0,1]

Output: [0,0,0,0,0,0,0,1,1,1,1,1]

(b.1) Implement (in Java) the RadixSort algorithm to sort (in increasing order) an array of nonnegative integer keys.

public void radixSort(int arr[])

In your implementation you must consider that each key contains only even digits (0, 2, 4, 6, and 8). Your program must detect the case of odd digits in the keys, and, in this case, your program must replace each odd digit by the greater even digit that is less than the odd digit. Examples: 3 2; 9 8; 1 0.

Example of the output of the program:

Input array

13, 4680, 24062, 51, 86, 642, 51, 426, 888,

After preprocessing (convert odd digits into even digits)

2, 4680, 24062, 40, 86, 642, 40, 426, 888,

Sorted array

2, 40, 40, 86, 426, 642, 888, 4680, 24062,

Note: To storage and process the bucket lists, use an ArrayList structure.

(b.2) What is the running time complexity of your radixSort method? Justify.

Explanation / Answer

//Answer for B2

let us COnsider N as total number of elements and consider the D as maximum number of digits.
approx complexity is O(D*N).

Justification:
In the radix sorting, for every digit is rearrange by the elements in given array.
Since there are N elements and D is max number of digit so maximum time complexity is O(D*N)

// Answer for B1

import java.util.ArrayList;
import java.util.Scanner;

public class RadixSrt {

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
ArrayList<Integer> arr = new ArrayList<>();
System.out.println("GIve size of the array");
int numOfElements = sc.nextInt();
System.out.println("Enter "+numOfElements+" elements with space separated");
for(int i=0;i<numOfElements;i++){
arr.add(sc.nextInt());
}
for(Integer i: arr){
if(!check(i)){
System.out.println("Aborting. Found a key having odd digit/s.");
System.exit(0);
}
}
radixSrt(arr);

}

private static boolean check(Integer key){
int k = key.intValue();
if(k==0)
return true;
while(k>0){
if(k%2==1)
return false;
k=k/10;
}
return true;
}

private static Integer maxElement(ArrayList<Integer> arr){
Integer mx = new Integer(0);
for(Integer i: arr){
if(i.intValue() > mx.intValue())
mx = i;
}
return mx;
}
private static void arranger(ArrayList<Integer> arr, int pow){
int len = arr.size();
ArrayList<Integer> newArr = new ArrayList<>(len);
ArrayList<Integer> bucket = new ArrayList<>();
for (int i=0;i<10;i++){
bucket.add(0);
}
for(int i=0;i<len;i++){
newArr.add(0);
int newEle = (arr.get(i).intValue()/pow)%10;
bucket.set(newEle,bucket.get(newEle).intValue()+1);
}

for(int i=1;i<10;i++){
bucket.set(i,bucket.get(i-1).intValue() + bucket.get(i).intValue());
}

for (int i=len-1;i>=0;i--){
int curr = (arr.get(i).intValue()/pow)%10;
newArr.set(bucket.get(curr)-1,arr.get(i));
bucket.set(curr,bucket.get(curr)-1);
}

for(int i=0;i<len;i++){
arr.set(i,newArr.get(i));
}
}

public static void radixSrt(ArrayList<Integer> arr){
int mx = maxElement(arr).intValue();
for(int i = 1;mx/i>0;i=i*10)
arranger(arr,i);
for(int i=0;i<arr.size();i++){
System.out.print(arr.get(i).intValue()+" ");
}
}
}

// Answer for a

import java.util.Arrays;

public class BitSrting {

public static void srt(int arr[]) {
int lft = 0, ryt = arr.length-1, tmp;
while (lft < ryt) {
if(arr[lft] == 0) {
lft++;
continue;
}
if(arr[ryt] == 1) {
ryt--;
continue;
}
tmp = arr[lft];
arr[lft] = arr[ryt];
arr[ryt] = tmp;
lft++;
ryt--;
}
}

public static void main(String[] args) {
int[] arr = {1,0,1,0,0,0,1,0,1,0,0,1};
srt(arr);
System.out.println(Arrays.toString(arr));
}

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.