instagram

QuickSort in Java with google interview question

This is an example of QuickSort in java. Below question was asked in google interview. The solution of this is Quicksort.

Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect.

public class QuickSorting {

	static int[] input = { -1, 1, 3, -2, 2 };

	public static void main(String args[]) {
		quickSort(0, input.length - 1);

		System.out.print("{ ");
		for (int i : input) {
			System.out.print(i + " ");
		}
		System.out.print("}");
	}

	public static void quickSort(int low, int high) {
		int i = low;
		int j = high;

		int pivot = input[(low + high) / 2];
		// You can use low + (High - Low )/2 to avoid overflow.
		while (i <= j) {

			while (input[i] < pivot) {
				i++;
			}

			while (input[j] > pivot) {
				j--;
			}

			if (i <= j) {
				int temp = input[i];
				input[i] = input[j];
				input[j] = temp;

				i++;
				j--;
			}

		}

		if (i < high) {
			quickSort(i, high);
		}

		if (j > low) {
			quickSort(low, j);
		}

	}

}
Share