This is a Java based solution to 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:
import java.util.Scanner;
public class Quicksort1_Partition {
public static void partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while (hi > lo) {
while (a[++i] < a[lo])
if (i == hi)
break;
while (a[--j] > a[lo])
if (j == lo)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, lo, j);
printSortedArray(a);
}
private static void swap(int array[], int i, int j) {
int tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
public static void printSortedArray(int a[]) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
partition(a, 0, a.length - 1);
sc.close();
}
}