# 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);
}

}

}
```