SHARE
TWEET

Untitled

a guest Sep 29th, 2013 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top