Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 29th, 2013  |  syntax: None  |  size: 7.72 KB  |  views: 41  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.*;
  2.  
  3. public class Sorting {
  4.  
  5.         public static final int MAX = 256000;
  6.  
  7.         /** Main method. */
  8.         static public void main(String[] args) {
  9.                 List<Integer> randlist = new ArrayList<Integer>(MAX); // original
  10.                 Random generaator = new Random();
  11.                 int maxKey = Math.min(1000, (MAX + 32) / 16);
  12.                 for (int i = 0; i < MAX; i++) {
  13.                         randlist.add(new Integer(generaator.nextInt(maxKey)));
  14.                 }
  15.  
  16.                 int rightLimit = randlist.size() / 16;
  17.  
  18.                 // Start a competition
  19.                 for (int round = 0; round < 4; round++) {
  20.                         rightLimit = 2 * rightLimit;
  21.                         System.out.println("\nLength: " + String.valueOf(rightLimit));
  22.  
  23.                         List<Integer> copy1 = new ArrayList<Integer>(randlist);
  24.                         long stime = new Date().getTime();
  25.                         insertionSort(copy1, 0, rightLimit);
  26.                         long ftime = new Date().getTime();
  27.                         int diff = new Long(ftime - stime).intValue();
  28.                         System.out.println("\nInsertion sort");
  29.                         System.out.println("Time (ms): " + String.valueOf(diff));
  30.                         if (!checkOrder(copy1, 0, rightLimit))
  31.                                 throw new RuntimeException("Wrong order!!!");
  32.                         List<Integer> copy2 = new ArrayList<Integer>(randlist);
  33.                         stime = new Date().getTime();
  34.                         biSort(copy2, 0, rightLimit);
  35.                         ftime = new Date().getTime();
  36.                         diff = new Long(ftime - stime).intValue();
  37.                         System.out.println("\nBinary insertion sort");
  38.                         System.out.println("Time (ms): " + String.valueOf(diff));
  39.                         if (!checkOrder(copy2, 0, rightLimit))
  40.                                 throw new RuntimeException("Wrong order!!!");
  41.                         List<Pair> opairs = new ArrayList<Pair>(MAX);
  42.                         for (int i = 0; i < randlist.size(); i++) {
  43.                                 opairs.add(new Pair(randlist.get(i), i));
  44.                         }
  45.                         biSort(opairs, 0, rightLimit);
  46.                         if (!checkStability(opairs, 0, rightLimit))
  47.                                 throw new RuntimeException("Method not stable!");
  48.                         List<Integer> copy3 = new ArrayList<Integer>(randlist);
  49.                         stime = new Date().getTime();
  50.                         qsort(copy3, 0, rightLimit);
  51.                         ftime = new Date().getTime();
  52.                         diff = new Long(ftime - stime).intValue();
  53.                         System.out.println("\nQuicksort");
  54.                         System.out.println("Time (ms): " + String.valueOf(diff));
  55.                         if (!checkOrder(copy3, 0, rightLimit))
  56.                                 throw new RuntimeException("Wrong order!!!");
  57.                         List<Integer> copy4 = new ArrayList<Integer>(randlist);
  58.                         Integer[] sarray = new Integer[rightLimit];
  59.                         sarray = (Integer[]) copy4.toArray(sarray);
  60.                         stime = new Date().getTime();
  61.                         Arrays.sort(sarray, 0, rightLimit);
  62.                         ftime = new Date().getTime();
  63.                         copy4 = Arrays.asList(sarray);
  64.                         diff = new Long(ftime - stime).intValue();
  65.                         System.out.println("\njava.util.Arrays");
  66.                         System.out.println("Time (ms): " + String.valueOf(diff));
  67.                         if (!checkOrder(copy4, 0, rightLimit))
  68.                                 throw new RuntimeException("Wrong order!!!");
  69.                         List<Integer> copy5 = new ArrayList<Integer>(randlist);
  70.                         copy5 = copy5.subList(0, rightLimit);
  71.                         stime = new Date().getTime();
  72.                         Collections.sort(copy5);
  73.                         ftime = new Date().getTime();
  74.                         diff = new Long(ftime - stime).intValue();
  75.                         System.out.println("\njava.util.Collections");
  76.                         System.out.println("Time (ms): " + String.valueOf(diff));
  77.                         if (!checkOrder(copy5, 0, rightLimit))
  78.                                 throw new RuntimeException("Wrong order!!!");
  79.                 }
  80.         } // main()
  81.  
  82.         /**
  83.          * Sort a part of the list using quicksort method.
  84.          *
  85.          * @param array
  86.          *            list
  87.          * @param l
  88.          *            starting index (included)
  89.          * @param r
  90.          *            ending index (excluded)
  91.          */
  92.         static public <T extends Object & Comparable<? super T>> void qsort(
  93.                         List<T> array, int l, int r) {
  94.                 if (array.size() < 2)
  95.                         return;
  96.                 if ((r - l) < 2)
  97.                         return;
  98.                 int i = l;
  99.                 int j = r - 1;
  100.                 T x = array.get((i + j) / 2);
  101.                 do {
  102.                         while (array.get(i).compareTo(x) < 0)
  103.                                 i++;
  104.                         while (x.compareTo(array.get(j)) < 0)
  105.                                 j--;
  106.                         if (i <= j) {
  107.                                 T tmp = array.get(i);
  108.                                 array.set(i, array.get(j));
  109.                                 array.set(j, tmp);
  110.                                 i++;
  111.                                 j--;
  112.                         }
  113.                 } while (i < j);
  114.                 if (l < j)
  115.                         qsort(array, l, j + 1); // recursion for left part
  116.                 if (i < r - 1)
  117.                         qsort(array, i, r); // recursion for right part
  118.         } // qsort()
  119.  
  120.         /**
  121.          * Sort a part of the list using binary insertion sort method in a stable
  122.          * manner.
  123.          *
  124.          * @param a
  125.          *            list
  126.          * @param left
  127.          *            starting position (included)
  128.          * @param right
  129.          *            ending position (excluded)
  130.          */
  131.         static public <T extends Object & Comparable<? super T>> void biSort(
  132.                         List<T> a, int left, int right) {
  133.  
  134.                 int mid, i, j;
  135.                 T v6ti;
  136.  
  137.                 right = a.size() - 1;
  138.                
  139.                 //binary searching
  140.                 for (i = left + 1; i <
  141.                                 left; i++) {
  142.  
  143.                         v6ti = a.remove(i);
  144.                         mid = (right - left) / 2;
  145.                         if (v6ti.compareTo((T) a.get(mid)) < 0)
  146.                                 right = mid - 1;
  147.                        
  148.                         if (v6ti.compareTo((T) a.get(mid)) > 0)
  149.  
  150.                                 left = mid + 1;
  151.  
  152.                         if (a.size() < 2)
  153.                                 return;
  154.                         if ((right - left) < 2)
  155.                                 return;
  156.  
  157.                         for (j = left; j < i; j++) {
  158.                                 if(v6ti.compareTo(a.get(j))==0) ;
  159.                                 if (v6ti.compareTo(a.get(j)) < 0)
  160.                                         break;
  161.                         }
  162.                         a.add(j, v6ti); // insert v6ti to position j
  163.  
  164.                 }
  165.  
  166.         }
  167.  
  168.        
  169.  
  170.         // TODO!!! Your code here!
  171.         // biSort()
  172.  
  173.         /**
  174.          * Sort a part of the list of comparable elements using insertion sort.
  175.          *
  176.          * @param a
  177.          *            list
  178.          * @param l
  179.          *            starting position (included)
  180.          * @param r
  181.          *            ending position (excluded)
  182.          */
  183.         static public <T extends Object & Comparable<? super T>> void insertionSort(
  184.                         List<T> a, int l, int r) {
  185.                 if (a.size() < 2)
  186.                         return;
  187.                 if ((r - l) < 2)
  188.                         return;
  189.                 for (int i = l + 1; i < r; i++) {
  190.                         T b = a.remove(i);
  191.                         int j;
  192.                         for (j = l; j < i; j++) {
  193.                                 if (b.compareTo(a.get(j)) < 0)
  194.                                         break;
  195.                         }
  196.                         a.add(j, b); // insert b to position j
  197.  
  198.                 }
  199.         } // insertionSort()
  200.  
  201.         /**
  202.          * Check whether a given interval in the list is ordered.
  203.          *
  204.          * @param a
  205.          *            sorted (?) list.
  206.          * @param l
  207.          *            left index (included)
  208.          * @param r
  209.          *            right index (excluded)
  210.          * @return interval is ordered?
  211.          */
  212.         static <T extends Object & Comparable<? super T>> boolean checkOrder(
  213.                         List<T> a, int l, int r) {
  214.                 if (a == null)
  215.                         throw new IllegalArgumentException();
  216.                 if (a.size() < 2)
  217.                         return true;
  218.                 if (l < 0 || r > a.size() || l >= r)
  219.                         throw new IllegalArgumentException();
  220.                 if (r - l < 2)
  221.                         return true;
  222.                 for (int i = l; i < r - 1; i++) {
  223.                         if (a.get(i).compareTo(a.get(i + 1)) > 0)
  224.                                 return false;
  225.                 } // for
  226.                 return true;
  227.         } // checkOrder()
  228.  
  229.         /** Is the list sorted in a stable manner. */
  230.         static boolean checkStability(List<Pair> a, int l, int r) {
  231.                 if (a == null)
  232.                         throw new IllegalArgumentException();
  233.                 if (a.size() < 2)
  234.                         return true;
  235.                 if (l < 0 || r > a.size() || l >= r)
  236.                         throw new IllegalArgumentException();
  237.                 if (r - l < 2)
  238.                         return true;
  239.                 for (int i = l; i < r - 1; i++) {
  240.                         if (a.get(i).compareTo(a.get(i + 1)) > 0)
  241.                                 return false;
  242.                         else if (a.get(i).compareTo(a.get(i + 1)) == 0) {
  243.                                 // System.out.print("=");
  244.                                 if (((Pair) a.get(i)).getSecundo() > ((Pair) a.get(i + 1))
  245.                                                 .getSecundo()) {
  246.                                         System.out.println("Method is not stable. First error: "
  247.                                                         + i + ". " + a.get(i) + " <--> " + (i + 1) + ". "
  248.                                                         + a.get(i + 1));
  249.                                         return false;
  250.                                 }
  251.                         }
  252.                 } // for
  253.                 return true;
  254.         }
  255. }
  256.  
  257. /** Local class to test stability. */
  258. class Pair implements Comparable<Pair> {
  259.  
  260.         private int primo;
  261.         private int secundo;
  262.  
  263.         Pair(int a, int b) {
  264.                 primo = a;
  265.                 secundo = b;
  266.         }
  267.  
  268.         public int getPrimo() {
  269.                 return primo;
  270.         }
  271.  
  272.         public int getSecundo() {
  273.                 return secundo;
  274.         }
  275.  
  276.         @Override
  277.         public String toString() {
  278.                 return "(" + String.valueOf(primo) + "," + String.valueOf(secundo)
  279.                                 + ")";
  280.         }
  281.  
  282.         public int compareTo(Pair o) {
  283.                 int esim = this.primo;
  284.                 int teine = ((Pair) o).primo;
  285.                 if (esim > teine)
  286.                         return 1;
  287.                 else if (esim < teine)
  288.                         return -1;
  289.                 else
  290.                         return 0;
  291.         }
  292. } // Pair
clone this paste RAW Paste Data