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 - QuickSort.java

QuickSort.java

Caricato da:
Scarica il programma completo

  1. package sort;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Hashtable;
  5. import java.util.Random;
  6.  
  7. public class QuickSort extends SortMethod {
  8.  
  9.     public static int RECURSION = 0;
  10.  
  11.     @Override
  12.     public Integer[] sort(Integer[] pArray) {
  13.         RECURSION++;
  14.         System.out.println("I'm a quick sort! " + RECURSION + "° Recursion!");
  15.         if (pArray.length <= 1) {
  16.             return pArray;
  17.         } else {
  18.             Random rand = new Random();
  19.             Integer k = rand.nextInt(pArray.length);
  20.             Integer pivot = pArray[k];
  21.             Hashtable<Integer, Integer[]> divide = QuickSort.divide(pArray, pivot, k);
  22.             Integer[] before = divide.get(0);
  23.             Integer[] after = divide.get(1);
  24.             before = this.sort(before);
  25.             after = this.sort(after);
  26.             return QuickSort.getReturnValue(before, after, pivot);
  27.         }
  28.     }
  29.  
  30.     private static Integer[] getReturnValue(Integer[] pBefore, Integer[] pAfter, Integer pivot) {
  31.         Integer[] retval = new Integer[pBefore.length + pAfter.length + 1];
  32.         int i = 0;
  33.         int before = 0;
  34.         int after = 0;
  35.         for (i = 0; i < pBefore.length; i++) {
  36.             retval[i] = pBefore[before];
  37.             before++;
  38.         }
  39.         retval[i] = pivot;
  40.         i++;
  41.         for (after = 0; after < pAfter.length; after++) {
  42.             retval[i] = pAfter[after];
  43.             i++;
  44.         }
  45.         return retval;
  46.     }
  47.  
  48.     private static Hashtable<Integer, Integer[]> divide(Integer[] pArray, Integer pivot, Integer pK) {
  49.         Hashtable<Integer, Integer[]> retval = new Hashtable<Integer, Integer[]>(2);
  50.         ArrayList<Integer> before = new ArrayList<Integer>();
  51.         ArrayList<Integer> after = new ArrayList<Integer>();
  52.         for (int i = 0; i < pArray.length; i++) {
  53.             if (i != pK) {
  54.                 if (pArray[i] < pivot) {
  55.                     before.add(pArray[i]);
  56.                 } else {
  57.                     after.add(pArray[i]);
  58.                 }
  59.             }
  60.         }
  61.         Integer[] beforeArr = new Integer[before.size()];
  62.         Integer[] afterArr = new Integer[after.size()];
  63.         before.toArray(beforeArr);
  64.         after.toArray(afterArr);
  65.         retval.put(0, beforeArr);
  66.         retval.put(1, afterArr);
  67.         return retval;
  68.     }
  69. }