×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Java
Posted by: Shamir Yona
Added: Jun 18, 2016 1:46 PM
Views: 11
Tags: java sort threads
Merge Sort using 2 threads.
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package moreTests;
  7.  
  8. import java.util.Arrays;
  9.  
  10. /**
  11.  *
  12.  * @author shayzukerman
  13.  */
  14. public class MergeSortByThreads implements ThreadWorkerClient
  15. {
  16.     int[] inpArr;
  17.     int N; // Size of the input array
  18.    
  19.     int[] tmpArr; //Helper array
  20.    
  21.     ThreadWorkersManager threadsManager;
  22.  
  23.     public MergeSortByThreads(int[] inpArr)
  24.     {
  25.         this.inpArr = inpArr;
  26.         N = inpArr.length;
  27.         tmpArr = new int[N];
  28.        
  29.         threadsManager = new ThreadWorkersManager(this, 2);
  30.     }
  31.    
  32.    
  33.     public void mergeSort()
  34.     {
  35.         //mergeSort_aux(0, N - 1, 0);
  36.         int min = 0;
  37.         int max = N - 1;
  38.         int mid = min + (max - min) / 2;
  39.         threadsManager.addWorkerThread(min, mid, true);
  40.         threadsManager.addWorkerThread(mid + 1, max, true);
  41.     }
  42.    
  43.     private void mergeSort_aux(int min, int max, int dbg_level)
  44.     {
  45.         printRange(min, max, String.format("start - level: %d ", dbg_level));
  46.         if (min >= max)
  47.             return;
  48.         int mid = min + (max - min) / 2;
  49.         mergeSort_aux(min, mid, dbg_level + 1);
  50.         mergeSort_aux(mid + 1, max, dbg_level + 1);
  51.         sortParts(min, mid, max);
  52.     }
  53.    
  54.     private void sortParts(int min, int mid, int max)
  55.     {
  56.         int i = min;
  57.         int j = mid + 1;
  58.         int k = 0;
  59.        
  60.         System.out.println("mid: " + mid);
  61.         printRange(min, max, "In sortParts - start");
  62.         Arrays.fill(tmpArr, 0);
  63.        
  64.         while (i <= mid && j <= max)
  65.         {
  66.             if (inpArr[i] < inpArr[j])
  67.             {
  68.                 tmpArr[k++] = inpArr[i];
  69.                 i++;
  70.             }
  71.             else
  72.             {
  73.                 tmpArr[k++] = inpArr[j];
  74.                 j++;
  75.             }
  76.         }
  77.         while (i <= mid)
  78.             tmpArr[k++] = inpArr[i++];
  79.  
  80.         while (j <= max)
  81.             tmpArr[k++] = inpArr[j++];
  82.            
  83.         System.arraycopy(tmpArr, 0, inpArr, min, max - min + 1);
  84.         printRange(min, max, "In sortParts - end");
  85.        
  86.     }
  87.    
  88.     private void printRange(int min, int max, String msg)
  89.     {
  90.         System.out.format("%s - min: %d max: %d - [", msg, min, max);
  91.         while (min <= max)
  92.         {
  93.             System.out.format("%d%s", inpArr[min], ((min < max) ? ", " : ""));
  94.             min++;
  95.         }
  96.         System.out.println("]");
  97.     }
  98.    
  99.     @Override
  100.     public int[] getArray()
  101.     {
  102.         return(this.inpArr);
  103.     }
  104.  
  105.     @Override
  106.     public void handleArray(int min, int max)
  107.     {
  108.         mergeSort_aux(min, max, 0);
  109.     }
  110.  
  111.     @Override
  112.     public void notifyReady()
  113.     {
  114.         System.out.println("Sort Merge threads are complete");
  115.         int min = 0;
  116.         int max = N - 1;
  117.         int mid = min + (N - 1 - min) / 2;
  118.         sortParts(min, mid, max);
  119.         printRange(0, inpArr.length - 1, "After sort");
  120.     }
  121.  
  122.  
  123.    
  124.    
  125.     public static void main(String[] args)
  126.     {
  127.         int[] inpArr = {8, 294, 20, 2,96, 1,6,3,9,4,1000, 5,10, 123};
  128.         //int[] inpArr = {3, 2, 4, 1};
  129.         MergeSortByThreads ms = new MergeSortByThreads(inpArr);
  130.         ms.mergeSort();
  131.     }
  132. }
  133.