Updating the correct code to sort array even with duplicate elements. The problem was in the way I was incrementing and decrementing the i and j pointers. In my previous code (if you see the previous revisions), I was doing the increment and decrement after the I check for the value and then performing the operation inside the while loop. In the…

QuickSortingAlgo.java

package com.algorithms;

import java.util.Random;

/**
 * Quicksort is popular because it is not difficult to implement, works well for
 * a variety of different kinds of input data, and is substantially faster than
 * any other sorting method in typical applications. It is in-place (uses only a
 * small auxiliary stack), requires time proportional to N log N on the average
 * to sort N items, and has an extremely short inner loop. The basic algorithm:
 * Quicksort is a divide-and-conquer method for sorting. It works by
 * partitioning an array into two parts, then sorting the parts independently.
 * 
 * The crux of the method is the partitioning process, which rearranges the
 * array to make the following three conditions hold: The entry a[j] is in its
 * final place in the array, for some j. No entry in a[lo] through a[j-1] is
 * greater than a[j]. No entry in a[j+1] through a[hi] is less than a[j].
 * 
 * We achieve a complete sort by partitioning, then recursively applying the
 * method to the subarrays. It is a randomized algorithm, because it randomly
 * shuffles the array before sorting it.
 * 
 * Input: 2 5 4 6 8 1 3 9 7 10
 * 
 * @author ThePathFinder
 * 
 */
public class QuickSortingAlgo {
	int[] arrayToSort;

	public QuickSortingAlgo(int[] a) {
		this.arrayToSort = a;
	}

	public QuickSortingAlgo() {
		// None
	}

	/**
	 * This API shuffles the array prior to sorting it using the Quick sort
	 * method.
	 * 
	 * @param a
	 * @return
	 */
	public int[] shuffle(int[] a) {
		Random rand = new Random();
		for (int i = 0; i < a.length; i++) {
			int toIndex = i + rand.nextInt(a.length - i);
			swap(a, i, toIndex);
		}
		return a;
	}

	private void swap(int[] a, int i, int toIndex) {
		System.out.print("Swapping " + i + " and " + toIndex + " = ");
		int temp = a[i];
		a[i] = a[toIndex];
		a[toIndex] = temp;
		for (int j = 0; j < a.length; j++)
			System.out.print(a[j] + ", ");
		System.out.println();
	}

	public int[] doQuickSort(int[] array) {
		// First shuffle the array
		array = shuffle(array);
		System.out.print("Array after Shuffle: ");
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + ", ");
		System.out.println();
		this.arrayToSort = doQuickSort(array, 0, array.length - 1);
		return this.arrayToSort;
	}

	private int[] doQuickSort(int[] array, int low, int hi) {
		// Now partition the array
		// Find a k such that elements left of a[k] are less than a[k], and,
		// elements right to it are greater.
		// Lets assume that the k is the first element of the array
		// System.out.println("Sorting...");
		if (hi < low)
			return array;

		int i = low;
		int j = hi + 1;
		int k = low;
		while (true) {
			while (array[++i] < array[k]) {
				//i++;
				if (i == hi)
					break;
			}
			while (array[--j] > array[k]) {
				//j--;
				if (j == low)
					break;
			}
			if (i >= j) break;
			
			swap(array, i, j);
		}

		swap(array, j, k);

		array = doQuickSort(array, 0, j - 1);
		array = doQuickSort(array, j + 1, hi);
		return array;
	}

	public static void main(String[] args) {
		int a[] = { 1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 8, 9, 10 };
		QuickSortingAlgo asA = new QuickSortingAlgo();
		System.out.print("Array before Sort: ");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + ", ");
		System.out.println();
		a = asA.doQuickSort(a);
		System.out.print("Array after Sort: ");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + ", ");
		System.out.println();
	}
}

This is an implementation of the Quick Sort Algorithm. This works for an array of integers with all unique elements. Please give comments and let me know if there is scope for optimization and make it efficient. As always, this is just some code I wrote for my revision of Algorithms concepts.