# Quicksortby Isai Damier, Android Engineer @ Google

```/*****************************************************************************
* Author: Isai Damier
* Title: QuickSort.java
* Project: geekviewpoint
* Package: algorithm.sorting
*
* Statement: Given a disordered list of integers (or any other items),
*  rearrange the integers in natural order.
*
* Sample Input: {8,5,3,1,9,6,0,7,4,2}
*
* Sample Output: {0,1,2,3,4,5,6,7,8,9}
*
* Time Complexity of Solution:
*  Best = Average = O(n*log(n)); Worst = O(n^2).
*
* Approach:
*  Quicksort is admirably known as the algorithm that sorts an array while
*  preparing to sort it. For contrast, recall that merge sort first
*  partitions an array into smaller pieces, then sorts each piece, then
*  merge the pieces back. Quicksort actually sorts the array during the
*  partition phase.
*
*  Quicksort works by selecting an element called a pivot and splitting the
*  array around that pivot such that all the elements in, say, the left
*  sub-array are less than pivot and all the elements in the right sub-array
*  are greater than pivot. The splitting continues until the array can no
*  longer be broken into pieces. That's it. Quicksort is done.
*
*  All this fussing about quicksort sorting while preparing to sort may give
*  the impression that it is better than mergesort, but its not. In practice
*  their time complexity is about the same -- with one funny exception.
*  Because quicksort picks its pivot randomly, there is a practically
*  impossible possibility that the algorithm may take O(n^2) to compute.
*
*  The aforementioned notwithstanding, quicksort is better than mergesort if
*  you consider memory usage. Quicksort is an in-place algorithm,
*  requiring no additional storage to work.
* **************************************************************************/
public void quicksort(int[] input) {
quicksort(input, 0, input.length - 1);
}

private void quicksort(int[] input, int first, int last) {
if (first < last) {
int pivot = partition(input, first, last);
quicksort(input, first, pivot - 1);
quicksort(input, pivot + 1, last);
}
}

private int partition(int[] input, int first, int last) {
int pivot = first + new Random().nextInt(last - first + 1);
swap(input, pivot, last);
for (int i = first; i < last; i++) {
if (input[i] <= input[last]) {
swap(input, i, first);
first++;
}
}
swap(input, first, last);
return first;
}

private void swap(int[] input, int a, int b) {
int tmp = input[a];
input[a] = input[b];
input[b] = tmp;
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

/**
* Test of quicksort method, of class Sorting.
*/
@Test
public void testQuicksort() {
System.out.println(""quicksort"");
int[] input = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
Sorting instance = new Sorting();
instance.quicksort(input);
for (int i = 1; i < input.length; i++) {
if (input[i - 1] > input[i]) {
fail(""quicksort method fails."");
}
}
System.out.println(Arrays.toString(input));
}
}```