HackerEarth Questions Asked on 9th June 2015

Q1) Chandu and his Girlfriend
---------------------------------------------------------------------------------

Chandu's girlfriend loves arrays that are sorted in non-increasing order. Today is her birthday. Chandu wants to give her some sorted arrays on her birthday. But the shop has only unsorted arrays. So, Chandu bought T unsorted arrays and is trying to sort them. But, he doesn't have much time to sort the arrays manually as he is getting late for the birthday party. So, he asked you to write a program to sort the T arrays in non-increasing order. Help him, or his girlfriend will kill him.

Input:
First line contains an integer T, denoting the number of test cases.
First line of each test case contains an integer N, denoting the size of the array.
Second line contains N space separated integers, denoting the array elements A_i.

Output:
For each test case, print the sorted array in non-increasing order.

Constraints:
1 <= T <= 100
1 <= N <= 10⁵
0 <= A_i <= 10⁹

Sample Input               Sample Output

2
5
2 5 2 4 3          5 4 3 2 2
5
5 4 2 3 1          5 4 3 2 1

Answer

---------------------------------------------------------------------------------

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Random;
public class Chandu_And_His_Girlfriend {
   public static void main(String args[] ) throws Exception {  
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         String line = br.readLine();
         int N = Integer.parseInt(line);
         for (int i = 0; i < N; i++) {
          line=br.readLine();
          int k=Integer.parseInt(line);
          int arr[]=new int[k];
          line=br.readLine();
          String str[]=line.split(" ");
           for(int p=0;p<str.length;p++){
            arr[p]=Integer.parseInt(str[p]);
           }
          int[] ser=quickSort(arr, 0,arr.length-1);
          for(int d=0;d<ser.length;d++){
           System.out.print(ser[d]+" ");
          }    System.out.println();
          }
      }

  public  static int partition(int[] arr1,int start,int end) {
   int pivot = arr1[end];
   int partitionIndex=start;
   for(int i=start;i<=end;i++){
    if(arr1[i]>pivot){
     int tmp=arr1[i];
     arr1[i]=arr1[partitionIndex];
     arr1[partitionIndex]=tmp;
     partitionIndex++;
    }
   }
   int tmp=arr1[partitionIndex];
   arr1[partitionIndex]=arr1[end];
   arr1[end]=tmp;
   return partitionIndex;
  }
  public static int[] quickSort(int[] arr1,int start,int end){
   if(start<end){
    int partitionIndex=partition(arr1, start, end);
    quickSort(arr1, start, partitionIndex-1);
    quickSort(arr1, partitionIndex+1, end);
   }
   return arr1;
  }
}