/* * To change this template, choose Tools | Templates * and open the template in the editor. */
package nguyenvanquan7826.temp;

/** * * @author john */
public class Temp {
	public Temp() {
		int i;
		int array[] = { 1, 3, 3, 3, 6, 7, 2, 4 };
		// int array[] = { 1, 3, 5, 8, 6, 7, 2, 4 };
		System.out.println(" Quick Sort\n");
		System.out.println("Values Before the sort:\n");
		for (i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		quickSort(array, 0, array.length - 1);
		System.out.print("\nValues after the sort:\n");
		for (i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
			System.out.print("");
			System.out.print(" ; ");
		}
	}

	void quickSort(int a[], int l, int r) {
		int key = a[(l + r) / 2]; // lay khoa la gia tri ngau nhien
									// tu a[l] -> a[r]
		// int key = a[(l+r)/2];
		int i = l, j = r;

		while (i <= j) {
			while (a[i] < key)
				i++; // tim phan tu ben trai ma >=key
			while (a[j] > key)
				j--; // tim phan tu ben trai ma <=key
			if (i <= j) {
				if (i < j) {
					int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
				i++;
				j--;
			}
		}
		// bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
		if (l < j)
			quickSort(a, l, j); // lam lai voi mang a[l]....a[j]
		if (i < r)
			quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
	}

	public static void main(String[] args) {
		new Temp();
	}
}