Hardik Vats Hardik Vats - 2 months ago 11
Java Question

Variant of Counting sort /Sorting algorithm

there is a problem which gives me a random number as a pivot, and i have to sort my array w.r.t to this pivot (closest come first then farthest)
for e.g.

array =[2,7,4,6,4,4,5,3,6,9,1,1,9] and

pivot=5

expected output: [5,4,4,6,6,3,7,2,1,1,9,9]


is this a variation of counting sort by any chance? if not ! can anyone give me a clue towards solving this problem?
I am encountering a roadblock in thinking on how to handle the counts and the array indices
Therefore, so far i have been able to do this

class HelloEclipse{

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int pivot=sc.nextInt();
int[] mainArray=new int[N];
int[] differenceArray=new int[N];
int[] differnceCountArray=new int[Integer.MAX_VALUE];
for(int i=0;i<N;i++){
mainArray[i]=sc.nextInt();
differenceArray[i]=pivot-mainArray[i];
if(differenceArray[i]>0){
differnceCountArray[differenceArray[i]]++;}
else{
differnceCountArray[-differenceArray[i]]++;
}

}
}
}


Any suggestions on how to proceed will be helpful!

Answer

Write a suitable Integer-Comparator and use Arays.sort:

public class PivotComparator implements Comparator<Integer> {

    private int pivot;

    public PivotComparator(int pivot) {
        super();
        this.pivot = pivot;
    }

    @Override
    public int compare(Integer a, Integer b) {
        return Math.abs(a - pivot) - Math.abs(b - pivot);
    }

    public static void main(String[] args) {

        Integer[] toSort = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        Comparator<Integer> comp = new PivotComparator(5);

        Arrays.sort(toSort, comp);
        for (Integer i : toSort) {
            System.out.println(i);
        }

    }

}