@@ -0,0 +1,1617 @@
+package sort;%0A%0A/*%0A%09This class implements quick sort on array of integers.%0A*/%0A%0Aclass QuickSort%7B%0A%0A%0A%0A%0A%09// Partitions array A between index p..r (inclusive) such that all elements %0A%09// smaller or equal to last element (index r) are on left and all elements%0A%09// greater than it are on right with index r element in middle, called pivot.%0A%09// Pivot element's index is returned.%0A%0A%09protected static int partition(int%5B%5D A, int p, int r)%7B%0A%0A%09%09int pivot = A%5Br%5D;%09%09%09// Pivot%0A%0A%09%09int i = p-1; %09%09%09// All elements upto index i would be less than pivot%09%09%09%0A%0A%09%09// For each element before pivot%0A%09%09for(int j=p;j%3Cr;j++)%7B%0A%0A%09%09%09// If element is less or equal (should appear on left)%0A%09%09%09if(A%5Bj%5D%3C=pivot)%7B%0A%09%09%09%09i++;%0A%0A%09%09%09%09// swap elements at index i and j%0A%09%09%09%09int t = A%5Bi%5D;%0A%09%09%09%09A%5Bi%5D = A%5Bj%5D;%0A%09%09%09%09A%5Bj%5D = t;%0A%09%09%09%7D%0A%0A%09%09%7D%0A%0A%09%09// Put pivot in its place (swap index i+1 and r)%0A%09%09int t = A%5Bi+1%5D;%0A%09%09A%5Bi+1%5D = A%5Br%5D;%0A%09%09A%5Br%5D = t;%0A%0A%09%09// Return pivot index%0A%09%09return i+1;%0A%0A%09%7D%0A%0A%0A%0A%09// Sorts array of integers A from index p to index r (inclusive)%0A%09// Time Complexity: %0A%09//%09%09%09%09%09Average Case: O( N.log(N) ) %09%0A%09// %09%09%09%09%09Worst Case: O( n*n )%0A%0A%09protected static void quicksort(int%5B%5D A, int p, int r)%7B%0A%0A%09%09// If there are more than one elements in the range p..r%0A%09%09if (p %3C r)%7B%0A%0A%09%09%09// Partition the range p..r%0A%09%09%09int q = partition(A, p, r);%0A%0A%09%09%09// Recursively sort two partitions%0A%09%09%09quicksort(A, p, q-1);%0A%09%09%09quicksort(A, q+1, r);%0A%0A%09%09%7D%0A%0A%09%7D%0A%0A%0A%09// Calls quicksort%0A%0A%09public static void sort(int A%5B%5D)%7B%0A%0A%09%09// If A is null or there are less than 2 elements in A, return%0A%09%09if (A == null %7C%7C A.length %3C2 )%0A%09%09%09return;%0A%0A%09%09// Otherwise, call quicksort%0A%09%09quicksort(A, 0, A.length-1);%0A%0A%0A%09%7D%0A%0A%0A%0A%7D%09

Add quick sort algorithm: