jain12

Shell Sort

Sep 27th, 2021
1,051
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class GFG {
  5.     // Driver code
  6.     public static void main(String[] args) throws Exception {
  7.         BufferedReader br =
  8.             new BufferedReader(new InputStreamReader(System.in));
  9.         int t = Integer.parseInt(br.readLine().trim());
  10.         while (t-- > 0) {
  11.             String inputLine[] = br.readLine().trim().split(" ");
  12.             int n = Integer.parseInt(inputLine[0]);
  13.             int m = Integer.parseInt(inputLine[1]);
  14.             int arr1[] = new int[n];
  15.             int arr2[] = new int[m];
  16.             inputLine = br.readLine().trim().split(" ");
  17.             for (int i = 0; i < n; i++) {
  18.                 arr1[i] = Integer.parseInt(inputLine[i]);
  19.             }
  20.             inputLine = br.readLine().trim().split(" ");
  21.             for (int i = 0; i < m; i++) {
  22.                 arr2[i] = Integer.parseInt(inputLine[i]);
  23.             }
  24.  
  25.             new Solution().merge(arr1, arr2, n, m);
  26.  
  27.             StringBuffer str = new StringBuffer();
  28.             for (int i = 0; i < n; i++) {
  29.                 str.append(arr1[i] + " ");
  30.             }
  31.             for (int i = 0; i < m; i++) {
  32.                 str.append(arr2[i] + " ");
  33.             }
  34.             System.out.println(str);
  35.         }
  36.     }
  37. }// } Driver Code Ends
  38.  
  39.  
  40. class Solution {
  41.  
  42.     public void merge(int arr1[], int arr2[], int n, int m) {
  43.         int gap=(n+m+1)/2;
  44.         for(;gap>0;gap/=2){
  45.             for(int j=gap;j<n+m;j++){
  46.                 int i=j;
  47.                 while(i>= gap && check(i,i-gap,arr1,arr2,n,m)){
  48.                     swap(i,i-gap,arr1,arr2,n,m);
  49.                     i-=gap;
  50.                     }
  51.                     /*
  52.                 if(check(i,i-gap,arr1,arr2,n,m)){
  53.                     swap(i,i-gap,arr1,arr2,n,m);
  54.                     }
  55.                     */
  56.                 }
  57.             }
  58.     }
  59.    
  60.     public boolean check(int i,int j,int[] arr1,int[] arr2,int n,int m){
  61.         //System.out.println(i+" "+j);
  62.         boolean check1=true,check2=true;
  63.         if(i>=n){
  64.             i=i-n;
  65.             check1=false;
  66.             }
  67.         if(j>=n){
  68.             j=j-n;
  69.             check2=false;
  70.             }
  71.         if(check1){
  72.             if(check2){
  73.                 return arr1[i]<arr1[j];
  74.                 }
  75.             else{
  76.                 return arr1[i]<arr2[j];
  77.                 }
  78.             }
  79.         else{
  80.              if(check2){
  81.                  return arr2[i]<arr1[j];
  82.                 }
  83.             else{
  84.                 return arr2[i]<arr2[j];
  85.                 }
  86.             }
  87.         }
  88.  
  89.     public void swap(int i,int j,int[] arr1,int[] arr2,int n,int m){
  90.         boolean check1=true,check2=true;
  91.         if(i>=n){
  92.             i=i-n;
  93.             check1=false;
  94.             }
  95.         if(j>=n){
  96.             j=j-n;
  97.             check2=false;
  98.             }
  99.         if(check1){
  100.             if(check2){
  101.                 int temp=arr1[i];
  102.                 arr1[i]=arr1[j];
  103.                 arr1[j]=temp;
  104.                 }
  105.             else{
  106.                 int temp2=arr1[i];
  107.                 arr1[i]=arr2[j];
  108.                 arr2[j]=temp2;
  109.                 }
  110.             }
  111.         else{
  112.              if(check2){
  113.                 int temp3=arr2[i];
  114.                 arr2[i]=arr1[j];
  115.                 arr1[j]=temp3;
  116.                 }
  117.             else{
  118.                 int temp4=arr2[i];
  119.                 arr2[i]=arr2[j];
  120.                 arr2[j]=temp4;
  121.                 }
  122.             }
  123.         }
  124. }
RAW Paste Data