Advertisement
GoodiesHQ

quicksort and merge

Sep 20th, 2016
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.54 KB | None | 0 0
  1. public class Dystopia {
  2.     // this is not merge sort... this will merge two arrays that are already sorted in ascending order
  3.     public static int[] mergeSorted(final int[] arr1, final int[] arr2){
  4.         final int a1len = arr1.length, a2len = arr2.length;
  5.         int[] ret = new int[a1len + a2len];
  6.         int a1cnt = 0, a2cnt = 0, retcnt = 0;
  7.  
  8.         while(a1cnt < arr1.length && a2cnt < arr2.length){
  9.             ret[retcnt++] = arr1[a1cnt] < arr2[a2cnt] ? arr1[a1cnt++] : arr2[a2cnt++];
  10.         }
  11.  
  12.         while(a1cnt < a1len) {
  13.             ret[retcnt++] = arr1[a1cnt++];
  14.         }
  15.  
  16.         while(a2cnt < a2len){
  17.             ret[retcnt++] = arr2[a2cnt++];
  18.         }
  19.  
  20.         return ret;
  21.     }
  22.  
  23.     public static void quicksort(int arr[]){
  24.         quicksort(arr, 0, arr.length - 1);
  25.     }
  26.  
  27.     public static void quicksort(int arr[], final int low, final int high){
  28.         if(arr == null || arr.length == 0 || low >= high){
  29.             return;
  30.         }
  31.  
  32.         int l = low, h = high;
  33.         final int pivot = arr[low + (high - low) / 2];           // get the middle term of the segment of arr[] requested
  34.         while(l <= h){
  35.             while(arr[l] < pivot){ ++l; }
  36.             while(arr[h] > pivot){ --h; }
  37.  
  38.             if(l <= h){
  39.                 int tmp = arr[l];
  40.                 arr[l++] = arr[h];
  41.                 arr[h--] = tmp;
  42.             }
  43.         }
  44.  
  45.         if(low < h) {
  46.             quicksort(arr, low, h);
  47.         }
  48.  
  49.         if(high > l){
  50.             quicksort(arr, l, high);
  51.         }
  52.  
  53.     }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement