Skip to content

HackerRank solutions – Quicksort 1 – Partition – Java Solution

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();

	}
}
, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.