Partition – Quicksort

We’re explaining a divide-and-conquer algorithm called Quicksort (also known as Partition Sort). This challenge is a modified version of the algorithm that only addresses partitioning. It is implemented as follows:

Partition Algorithm

• Choose some pivot element, p, and partition your unsorted array, arr, into three smaller arrays: left, right, and equal, where each element in left < p, each element in right > p, and each element in equal = p.
• For example: Assume arr = [6,4,1,3,8,7,9]
• The pivot is at arr[0] = 6
• arr is divided into left={3,4,1}, equals={6}, and right={8,7,9} 
• Putting them all together, you get {3,4,1,6,8,7,9}. Another valid solution is {1,3,4,6,8,7,9}.
• Given arr and p = arr[0], partition arr into left, right, and equals using the Divide instructions above. Then print each element in left followed by each element in equal, followed by each element in right on a single line. Your output should be space-separated and does not have to maintain ordering of the elements within the three categories.

Input Format

The scanner’s input string has two lines.

• The first line contains n, the size of the array arr.
• The second line contains n space-separated integers describing arr(the unsorted array). The first integer (corresponding to arr[0]) is your pivot element, p.

Output Format

On a single line, print the partitioned numbers (i.e.: the elements in left, then the elements in equal, and then the elements in right). Each integer should be separated by a single space.

7
6 4 1 3 8 7 9

3 4 1 6 8 7 9

Explanation

We then print the elements of left, followed by equal, followed by right, we get: 3 4 1 6 8 7 9.
You don’t need to maintain ordering, so another valid solution would be 1 3 4 6 7 8 9.

QuicksortPartition Program

package com.hi.techpoints.algorithms;

import java.util.Scanner;

/**
 * @author elavarasan_pk
 *
 */
public class QuicksortPartition {

	
	/** Performing quickSort
	 * @param arr
	 */
	public static void partition(int[] arr) {
		int zero = 0, 
			size = arr.length - 1, 
			leftIndex = zero, //Assigning left index as ZERO
			rightIndex = size + 1,//Assigning right index as actual array input size.
			pivot = arr[zero];
		while (size > zero) {
			while (arr[++leftIndex] < pivot) {
				if (leftIndex == size)
					break;
			}
			while (arr[--rightIndex] > pivot) {
				if (rightIndex == zero)
					break;
			}
			if (leftIndex >= rightIndex) {
				break;
			}
			swap(arr, leftIndex, rightIndex);

		}
		swap(arr, zero, rightIndex);
		printArray(arr);
	}

	/** if rightIndex array is less than pivot value,
	 * Swapping the rightIndex value  to leftIndex position array.   
	 * @param array
	 * @param i
	 * @param j
	 */
	private static void swap(int arr[], int i, int j) {
		int temp = arr[j];
		arr[j] = arr[i];
		arr[i] = temp;
	}

	/** After quick sort, Print output on single line.
	 * @param arr
	 */
	public static void printArray(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			System.out.format("%d ", arr[i]);
		}
	}

	public static void main(String[] args) {
		String input = "7 \n" //Input array size.
				      + "6 4 1 3 8 7 9";//Array values.
		Scanner sc = new Scanner(input);
		int N = sc.nextInt();
		int arr[] = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		partition(arr);
		sc.close();

	}
}