// Path: Java-data-Structures/src/main/java/com/sorting/QuickSort.java
// public class QuickSort {
// 
//     /**
//      * Use the Quicksort method to sort the given array A
//      * 
//      * @param A
//      *            Array of Comparable that contains the object to sort
//      */
//     public static void sort(Comparable[] A) {
//         if (A == null)
//             return;
//         shuffle(A);
//         sort(A, 0, A.length - 1);
//     }
// 
//     private static void sort(Comparable[] A, int lo, int hi) {
//         if (lo >= hi)
//             return;
//         int k = partition(A, lo, hi);
//         sort(A, lo, k - 1);
//         sort(A, k + 1, hi);
//     }
// 
//     private static int partition(Comparable[] A, int lo, int hi) {
//         int i = lo + 1;
//         int j = hi;
//         while (true) {
//             while ((i < j) && !less(A[lo], A[i]))
//                 i++;
//             while (less(A[lo], A[j]))
//                 j--;
//             if (i >= j)
//                 break;
//             swap(A, i, j);
//             i++;
//             j--;
//         }
//         swap(A, lo, j);
//         return j;
//     }
// 
//     private static void shuffle(Comparable[] A) {
//         Random rdm = new Random();
//         int r = 0;
//         for (int i = 0; i < A.length; i++) {
//             r = rdm.nextInt(i + 1);
//             swap(A, i, r);
//         }
//     }
// 
//     private static void swap(Comparable[] A, int i, int j) {
//         Comparable k = A[i];
//         A[i] = A[j];
//         A[j] = k;
//     }
// 
//     private static boolean less(Comparable a, Comparable b) {
//         int cmp = a.compareTo(b);
//         if (cmp < 0)
//             return true;
//         return false;
//     }
// 
//     private static boolean equals(Comparable a, Comparable b) {
//         int cmp = a.compareTo(b);
//         if (cmp == 0)
//             return true;
//         return false;
//     }
// }


import com.sorting.QuickSort;
import junit.framework.TestCase;
package com.test.sorting;



public class TestQuickSort extends TestCase {

    public void testQuickSort() {

        String[] A = { "zs", "qw", "qr", "miguel", "rtd", "fgs", "qq", "mk", "slao", "oiu", "vf", "xs", "er", "qw",
                "bv" };
        Integer[] B = { 2, 4, 7, 542, 0, 1, 3, 0, 6, 2, 7, 9, 10, 2, 4, 6, 0, 3, 2, 9, 2, 77, 33, 22, 5, 4, 2, 2, 2 };

// Path: Java-data-Structures/src/main/java/com/sorting/QuickSort.java
// public class QuickSort {
// 
//     /**
//      * Use the Quicksort method to sort the given array A
//      * 
//      * @param A
//      *            Array of Comparable that contains the object to sort
//      */
//     public static void sort(Comparable[] A) {
//         if (A == null)
//             return;
//         shuffle(A);
//         sort(A, 0, A.length - 1);
//     }
// 
//     private static void sort(Comparable[] A, int lo, int hi) {
//         if (lo >= hi)
//             return;
//         int k = partition(A, lo, hi);
//         sort(A, lo, k - 1);
//         sort(A, k + 1, hi);
//     }
// 
//     private static int partition(Comparable[] A, int lo, int hi) {
//         int i = lo + 1;
//         int j = hi;
//         while (true) {
//             while ((i < j) && !less(A[lo], A[i]))
//                 i++;
//             while (less(A[lo], A[j]))
//                 j--;
//             if (i >= j)
//                 break;
//             swap(A, i, j);
//             i++;
//             j--;
//         }
//         swap(A, lo, j);
//         return j;
//     }
// 
//     private static void shuffle(Comparable[] A) {
//         Random rdm = new Random();
//         int r = 0;
//         for (int i = 0; i < A.length; i++) {
//             r = rdm.nextInt(i + 1);
//             swap(A, i, r);
//         }
//     }
// 
//     private static void swap(Comparable[] A, int i, int j) {
//         Comparable k = A[i];
//         A[i] = A[j];
//         A[j] = k;
//     }
// 
//     private static boolean less(Comparable a, Comparable b) {
//         int cmp = a.compareTo(b);
//         if (cmp < 0)
//             return true;
//         return false;
//     }
// 
//     private static boolean equals(Comparable a, Comparable b) {
//         int cmp = a.compareTo(b);
//         if (cmp == 0)
//             return true;
//         return false;
//     }
// }


// Path: Java-data-Structures/src/test/java/com/test/sorting/TestQuickSort.java
import com.sorting.QuickSort;
import junit.framework.TestCase;

package com.test.sorting;



public class TestQuickSort extends TestCase {

    public void testQuickSort() {

        String[] A = { "zs", "qw", "qr", "miguel", "rtd", "fgs", "qq", "mk", "slao", "oiu", "vf", "xs", "er", "qw",
                "bv" };
        Integer[] B = { 2, 4, 7, 542, 0, 1, 3, 0, 6, 2, 7, 9, 10, 2, 4, 6, 0, 3, 2, 9, 2, 77, 33, 22, 5, 4, 2, 2, 2 };

        QuickSort.sort(A);