Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.List;
- import java.util.ArrayList;
- import java.util.Random;
- import java.util.Comparator;
- import static java.util.Collections.swap ;
- public class QuickSortTest {
- private static final Random generator = new Random();
- public static<T extends Comparable<? super T>>
- int ascending(T t1, T t2) {
- return t1.compareTo(t2);
- }
- public static<T extends Comparable<? super T>>
- int descending(T t1, T t2) {
- return -ascending(t1, t2);
- }
- public static void main(String[] args) {
- List<Integer> list = new ArrayList<Integer>();
- int size = 10;
- for (int i = 0; i < size; i++) {
- list.add(1 + generator.nextInt(10));
- }
- System.out.println(list);
- quickSort(list, 0, list.size() - 1, QuickSortTest::ascending);
- System.out.println(list);
- }
- public static<T> void quickSort(
- List<T> list, int left, int right, Comparator<? super T> c) {
- if (left < right) {
- int index = partition(list, left, right, c);
- quickSort(list, left, index - 1, c);
- quickSort(list, index + 1, right, c);
- }
- }
- public static<T> int partition(
- List<T> list, int left, int right, Comparator<? super T> c) {
- T axis = list.get(left);
- int index = partitionUnprocessed(list, left + 1, right, axis, c);
- swap(list, left, index);
- return index;
- }
- public static<T> int partitionUnprocessed(
- List<T> list, int left, int right, T axis, Comparator<? super T> c) {
- int i = lookRight(list, left, right, axis, c);
- int j = lookLeft(list, right, i, axis, c);
- if (i < j) {
- swap(list, i, j);
- return partitionUnprocessed(list, i + 1, j - 1, axis, c);
- }
- else {
- return j;
- }
- }
- public static<T> int lookRight(
- List<T> list, int index, int to, T axis, Comparator<? super T> c) {
- if (index < to + 1 && c.compare(list.get(index), axis) <= 0) {
- return lookRight(list, index + 1, to, axis, c);
- }
- else {
- return index;
- }
- }
- public static<T> int lookLeft(
- List<T> list, int index, int to, T axis, Comparator<? super T> c) {
- if (index > to - 1 && c.compare(list.get(index), axis) > 0) {
- return lookLeft(list, index - 1, to, axis, c);
- }
- else {
- return index;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment