Guest User

Quick Sort in Java

a guest
Aug 20th, 2013
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.62 KB | None | 0 0
  1. import java.util.List;
  2. import java.util.ArrayList;
  3. import java.util.Random;
  4. import java.util.Comparator;
  5. import static java.util.Collections.swap ;
  6.  
  7. public class QuickSortTest {
  8.     private static final Random generator = new Random();
  9.  
  10.     public static<T extends Comparable<? super T>>
  11.         int ascending(T t1, T t2) {
  12.             return t1.compareTo(t2);
  13.         }
  14.  
  15.     public static<T extends Comparable<? super T>>
  16.         int descending(T t1, T t2) {
  17.             return -ascending(t1, t2);
  18.         }
  19.  
  20.     public static void main(String[] args) {
  21.         List<Integer> list = new ArrayList<Integer>();
  22.  
  23.         int size = 10;
  24.  
  25.         for (int i = 0; i < size; i++) {
  26.             list.add(1 + generator.nextInt(10));
  27.         }
  28.  
  29.         System.out.println(list);
  30.  
  31.         quickSort(list, 0, list.size() - 1, QuickSortTest::ascending);
  32.  
  33.         System.out.println(list);
  34.     }
  35.  
  36.  
  37.     public static<T> void quickSort(
  38.         List<T> list, int left, int right, Comparator<? super T> c) {
  39.             if (left < right) {
  40.                 int index = partition(list, left, right, c);
  41.                 quickSort(list, left, index - 1, c);
  42.                 quickSort(list, index + 1, right, c);
  43.             }
  44.         }
  45.  
  46.     public static<T> int partition(
  47.         List<T> list, int left, int right, Comparator<? super T> c) {
  48.             T axis = list.get(left);
  49.             int index = partitionUnprocessed(list, left + 1, right, axis, c);
  50.             swap(list, left, index);
  51.             return index;
  52.         }
  53.  
  54.     public static<T> int partitionUnprocessed(
  55.         List<T> list, int left, int right, T axis, Comparator<? super T> c) {
  56.             int i = lookRight(list, left, right, axis, c);
  57.             int j = lookLeft(list, right, i, axis, c);
  58.  
  59.             if (i < j) {
  60.                 swap(list, i, j);
  61.                 return partitionUnprocessed(list, i + 1, j - 1, axis, c);
  62.             }
  63.             else {
  64.                 return j;
  65.             }
  66.         }
  67.  
  68.     public static<T> int lookRight(
  69.         List<T> list, int index, int to, T axis, Comparator<? super T> c) {
  70.         if (index < to + 1 && c.compare(list.get(index), axis) <= 0) {
  71.             return lookRight(list, index + 1, to, axis, c);
  72.         }
  73.         else {
  74.             return index;
  75.         }
  76.     }
  77.  
  78.     public static<T> int lookLeft(
  79.         List<T> list, int index, int to, T axis, Comparator<? super T> c) {
  80.         if (index > to - 1 && c.compare(list.get(index), axis) > 0) {
  81.             return lookLeft(list, index - 1, to, axis, c);
  82.         }
  83.         else {
  84.             return index;
  85.         }
  86.     }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment