Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Sort - InsertSort.java

InsertSort.java

Caricato da:
Scarica il programma completo

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