Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Sorting {
- public static final int MAX = 256000;
- /** Main method. */
- static public void main(String[] args) {
- List<Integer> randlist = new ArrayList<Integer>(MAX); // original
- Random generaator = new Random();
- int maxKey = Math.min(1000, (MAX + 32) / 16);
- for (int i = 0; i < MAX; i++) {
- randlist.add(new Integer(generaator.nextInt(maxKey)));
- }
- int rightLimit = randlist.size() / 16;
- // Start a competition
- for (int round = 0; round < 4; round++) {
- rightLimit = 2 * rightLimit;
- System.out.println("\nLength: " + String.valueOf(rightLimit));
- List<Integer> copy1 = new ArrayList<Integer>(randlist);
- long stime = new Date().getTime();
- insertionSort(copy1, 0, rightLimit);
- long ftime = new Date().getTime();
- int diff = new Long(ftime - stime).intValue();
- System.out.println("\nInsertion sort");
- System.out.println("Time (ms): " + String.valueOf(diff));
- if (!checkOrder(copy1, 0, rightLimit))
- throw new RuntimeException("Wrong order!!!");
- List<Integer> copy2 = new ArrayList<Integer>(randlist);
- stime = new Date().getTime();
- biSort(copy2, 0, rightLimit);
- ftime = new Date().getTime();
- diff = new Long(ftime - stime).intValue();
- System.out.println("\nBinary insertion sort");
- System.out.println("Time (ms): " + String.valueOf(diff));
- if (!checkOrder(copy2, 0, rightLimit))
- throw new RuntimeException("Wrong order!!!");
- List<Pair> opairs = new ArrayList<Pair>(MAX);
- for (int i = 0; i < randlist.size(); i++) {
- opairs.add(new Pair(randlist.get(i), i));
- }
- biSort(opairs, 0, rightLimit);
- if (!checkStability(opairs, 0, rightLimit))
- throw new RuntimeException("Method not stable!");
- List<Integer> copy3 = new ArrayList<Integer>(randlist);
- stime = new Date().getTime();
- qsort(copy3, 0, rightLimit);
- ftime = new Date().getTime();
- diff = new Long(ftime - stime).intValue();
- System.out.println("\nQuicksort");
- System.out.println("Time (ms): " + String.valueOf(diff));
- if (!checkOrder(copy3, 0, rightLimit))
- throw new RuntimeException("Wrong order!!!");
- List<Integer> copy4 = new ArrayList<Integer>(randlist);
- Integer[] sarray = new Integer[rightLimit];
- sarray = (Integer[]) copy4.toArray(sarray);
- stime = new Date().getTime();
- Arrays.sort(sarray, 0, rightLimit);
- ftime = new Date().getTime();
- copy4 = Arrays.asList(sarray);
- diff = new Long(ftime - stime).intValue();
- System.out.println("\njava.util.Arrays");
- System.out.println("Time (ms): " + String.valueOf(diff));
- if (!checkOrder(copy4, 0, rightLimit))
- throw new RuntimeException("Wrong order!!!");
- List<Integer> copy5 = new ArrayList<Integer>(randlist);
- copy5 = copy5.subList(0, rightLimit);
- stime = new Date().getTime();
- Collections.sort(copy5);
- ftime = new Date().getTime();
- diff = new Long(ftime - stime).intValue();
- System.out.println("\njava.util.Collections");
- System.out.println("Time (ms): " + String.valueOf(diff));
- if (!checkOrder(copy5, 0, rightLimit))
- throw new RuntimeException("Wrong order!!!");
- }
- } // main()
- /**
- * Sort a part of the list using quicksort method.
- *
- * @param array
- * list
- * @param l
- * starting index (included)
- * @param r
- * ending index (excluded)
- */
- static public <T extends Object & Comparable<? super T>> void qsort(
- List<T> array, int l, int r) {
- if (array.size() < 2)
- return;
- if ((r - l) < 2)
- return;
- int i = l;
- int j = r - 1;
- T x = array.get((i + j) / 2);
- do {
- while (array.get(i).compareTo(x) < 0)
- i++;
- while (x.compareTo(array.get(j)) < 0)
- j--;
- if (i <= j) {
- T tmp = array.get(i);
- array.set(i, array.get(j));
- array.set(j, tmp);
- i++;
- j--;
- }
- } while (i < j);
- if (l < j)
- qsort(array, l, j + 1); // recursion for left part
- if (i < r - 1)
- qsort(array, i, r); // recursion for right part
- } // qsort()
- /**
- * Sort a part of the list using binary insertion sort method in a stable
- * manner.
- *
- * @param a
- * list
- * @param left
- * starting position (included)
- * @param right
- * ending position (excluded)
- */
- static public <T extends Object & Comparable<? super T>> void biSort(
- List<T> a, int left, int right) {
- int mid, i, j;
- T v6ti;
- right = a.size() - 1;
- //binary searching
- for (i = left + 1; i <
- left; i++) {
- v6ti = a.remove(i);
- mid = (right - left) / 2;
- if (v6ti.compareTo((T) a.get(mid)) < 0)
- right = mid - 1;
- if (v6ti.compareTo((T) a.get(mid)) > 0)
- left = mid + 1;
- if (a.size() < 2)
- return;
- if ((right - left) < 2)
- return;
- for (j = left; j < i; j++) {
- if(v6ti.compareTo(a.get(j))==0) ;
- if (v6ti.compareTo(a.get(j)) < 0)
- break;
- }
- a.add(j, v6ti); // insert v6ti to position j
- }
- }
- // TODO!!! Your code here!
- // biSort()
- /**
- * Sort a part of the list of comparable elements using insertion sort.
- *
- * @param a
- * list
- * @param l
- * starting position (included)
- * @param r
- * ending position (excluded)
- */
- static public <T extends Object & Comparable<? super T>> void insertionSort(
- List<T> a, int l, int r) {
- if (a.size() < 2)
- return;
- if ((r - l) < 2)
- return;
- for (int i = l + 1; i < r; i++) {
- T b = a.remove(i);
- int j;
- for (j = l; j < i; j++) {
- if (b.compareTo(a.get(j)) < 0)
- break;
- }
- a.add(j, b); // insert b to position j
- }
- } // insertionSort()
- /**
- * Check whether a given interval in the list is ordered.
- *
- * @param a
- * sorted (?) list.
- * @param l
- * left index (included)
- * @param r
- * right index (excluded)
- * @return interval is ordered?
- */
- static <T extends Object & Comparable<? super T>> boolean checkOrder(
- List<T> a, int l, int r) {
- if (a == null)
- throw new IllegalArgumentException();
- if (a.size() < 2)
- return true;
- if (l < 0 || r > a.size() || l >= r)
- throw new IllegalArgumentException();
- if (r - l < 2)
- return true;
- for (int i = l; i < r - 1; i++) {
- if (a.get(i).compareTo(a.get(i + 1)) > 0)
- return false;
- } // for
- return true;
- } // checkOrder()
- /** Is the list sorted in a stable manner. */
- static boolean checkStability(List<Pair> a, int l, int r) {
- if (a == null)
- throw new IllegalArgumentException();
- if (a.size() < 2)
- return true;
- if (l < 0 || r > a.size() || l >= r)
- throw new IllegalArgumentException();
- if (r - l < 2)
- return true;
- for (int i = l; i < r - 1; i++) {
- if (a.get(i).compareTo(a.get(i + 1)) > 0)
- return false;
- else if (a.get(i).compareTo(a.get(i + 1)) == 0) {
- // System.out.print("=");
- if (((Pair) a.get(i)).getSecundo() > ((Pair) a.get(i + 1))
- .getSecundo()) {
- System.out.println("Method is not stable. First error: "
- + i + ". " + a.get(i) + " <--> " + (i + 1) + ". "
- + a.get(i + 1));
- return false;
- }
- }
- } // for
- return true;
- }
- }
- /** Local class to test stability. */
- class Pair implements Comparable<Pair> {
- private int primo;
- private int secundo;
- Pair(int a, int b) {
- primo = a;
- secundo = b;
- }
- public int getPrimo() {
- return primo;
- }
- public int getSecundo() {
- return secundo;
- }
- @Override
- public String toString() {
- return "(" + String.valueOf(primo) + "," + String.valueOf(secundo)
- + ")";
- }
- public int compareTo(Pair o) {
- int esim = this.primo;
- int teine = ((Pair) o).primo;
- if (esim > teine)
- return 1;
- else if (esim < teine)
- return -1;
- else
- return 0;
- }
- } // Pair
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement