Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Sort - MergeSort.java

MergeSort.java

Caricato da:
Scarica il programma completo

  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5. package sort;
  6.  
  7. import java.util.Hashtable;
  8.  
  9. /**
  10.  *
  11.  * @author Paolo
  12.  */
  13. public class MergeSort extends SortMethod {
  14.  
  15.     public static int RECURSION=0;
  16.  
  17.     @Override
  18.     public Integer[] sort(Integer[] pArray) {
  19.         RECURSION++;
  20.         System.out.println("I'm a merge sort! "+RECURSION+"° Recursion!");
  21.         if (pArray.length == 1) {
  22.             return pArray;
  23.         } else if (pArray.length == 2) {
  24.             int swap = 0;
  25.             if (pArray[0] > pArray[1]) {
  26.                 swap = pArray[0];
  27.                 pArray[0] = pArray[1];
  28.                 pArray[1] = swap;
  29.             }
  30.             return pArray;
  31.         }
  32.         Hashtable<Integer, Integer[]> divide = this.divide(pArray);
  33.         Integer[] first = divide.get(0);
  34.         Integer[] second = divide.get(1);
  35.         first = this.sort(first);
  36.         second = this.sort(second);
  37.         pArray = this.merge(first, second);
  38.         return pArray;
  39.     }
  40.  
  41.     private Hashtable<Integer, Integer[]> divide(Integer[] pArray) {
  42.         Hashtable<Integer, Integer[]> retval = new Hashtable<Integer, Integer[]>(2);
  43.         boolean eval = pArray.length % 2 == 1;
  44.         Integer[] first = new Integer[pArray.length / 2];
  45.         Integer[] second = eval ? new Integer[(pArray.length / 2) + 1] : new Integer[pArray.length / 2];
  46.         for (int i = 0; i < pArray.length / 2; i++) {
  47.             first[i] = pArray[i];
  48.             second[i] = pArray[i + pArray.length / 2];
  49.         }
  50.         if (eval) {
  51.             second[second.length - 1] = pArray[pArray.length - 1];
  52.         }
  53.         retval.put(0, first);
  54.         retval.put(1, second);
  55.         return retval;
  56.     }
  57.  
  58.     private Integer[] merge(Integer[] pFirst, Integer[] pSecond) {
  59.         Integer[] retval = new Integer[pFirst.length + pSecond.length];
  60.         int first = 0;
  61.         int second = 0;
  62.         boolean oneEnd=false;
  63.         int i=0;
  64.         for (i = 0; i < retval.length && !oneEnd; i++) {
  65.             if (pFirst[first] < pSecond[second]) {
  66.                 retval[i] = pFirst[first];
  67.                 first++;
  68.             } else {
  69.                 retval[i] = pSecond[second];
  70.                 second++;
  71.             }
  72.             oneEnd=first>=pFirst.length || second>=pSecond.length;
  73.         }
  74.         if(first<second){
  75.             for(;first<pFirst.length; first++){
  76.                 retval[i]=pFirst[first];
  77.                 i++;
  78.             }
  79.         }else{
  80.             for(;second<pSecond.length; second++){
  81.                 retval[i]=pSecond[second];
  82.                 i++;
  83.             }            
  84.         }
  85.         return retval;
  86.     }
  87. }