@@ -0,0 +1,2190 @@
+package Sorting;%0A%0Aimport java.util.Arrays; // Only used for testing%0Aimport java.util.Comparator;%0Aimport java.util.Random;%0A%0Apublic class QuickSort %7B%0A%0A    public static %3CT extends Comparable%3CT%3E%3E void sort(T%5B%5D arr) %7B%0A        sort(arr, Comparator.naturalOrder());%0A    %7D%0A%0A    public static %3CT%3E void sort(T%5B%5D arr, Comparator%3CT%3E comparator) %7B%0A        sortRange(arr, 0, arr.length, comparator);%0A    %7D%0A%0A    private static %3CT%3E void sortRange(T%5B%5D arr, int from, int to, Comparator%3CT%3E comparator) %7B%0A        if (to - from %3E 1) %7B%0A            int randomPivot = new Random().nextInt(to - from) + from;%0A            swap(arr, randomPivot, to - 1);%0A%0A            T pivot = arr%5Bto - 1%5D;%0A            int middle = from;%0A%0A            for (int i = from; i %3C to - 1; i++) %7B%0A                if (comparator.compare(arr%5Bi%5D, pivot) %3C 0) %7B%0A                    swap(arr, middle, i);%0A                    middle++;%0A                %7D%0A            %7D%0A%0A            swap(arr, middle, to - 1);%0A%0A            sortRange(arr, from, middle, comparator);%0A            sortRange(arr, middle + 1, to, comparator);%0A        %7D%0A    %7D%0A%0A    private static %3CT%3E void swap(T%5B%5D arr, int i, int j) %7B%0A        T temp = arr%5Bi%5D;%0A        arr%5Bi%5D = arr%5Bj%5D;%0A        arr%5Bj%5D = temp;%0A    %7D%0A%0A%0A    public static void main(String%5B%5D args) %7B%0A        // Testing sort giving class Integer that has a compareTo method%0A        Integer%5B%5D test = new Integer%5B%5D%7B5, 2, 24, 8, 1, 36, 42, 80, 20, 56%7D;%0A        sort(test);%0A        System.out.println(Arrays.deepToString(test));%0A%0A        System.out.println();%0A%0A        // Testing sort giving class Dog that does not have a compareTo method%0A        Dog%5B%5D test2 = new Dog%5B%5D%7B%0A                new Dog(%22Carl%22, 3),%0A                new Dog(%22Wuffer%22, 4),%0A                new Dog(%22Carl%22, 4),%0A                new Dog(%22Irena%22, 2)%0A        %7D;%0A        sort(test2, (dog1, dog2) -%3E (dog1.name.compareTo(dog2.name)));%0A        System.out.println(Arrays.deepToString(test2));%0A    %7D%0A%0A    private static class Dog %7B%0A        String name;%0A        int age;%0A%0A        Dog(String name, int age) %7B%0A            this.name = name;%0A            this.age = age;%0A        %7D%0A%0A        public String toString() %7B%0A            return name + %22 %22 + age;%0A        %7D%0A    %7D%0A%0A%7D%0A

Implement Generic QuickSort