# Quick Sort in Java

Quick sort is a sorting algorithm, used in data structures for sorting arrays, queues, linked lists and other linear data structures. Quick sort works on the principle of Divide and Conquer. Quick sort is also known as partition-exchange sort.

 Time Complexity O(n log n) Best Case O(n log n) Worst Case O(n2) Space Complexity O(1) Auxiliary Space Complexity O(log n) In Place Yes Stable No

# Quick Sort in Java

• Choose the pivot element.
• Move the elements smaller to pivot in the left partition
• Move the elements greater than pivot to the right partition
• The partition index is discovered at the end

New pivot is then chosen in each of the partition and the above steps are repeated until partitions of one item each is reached.

Generally, pivot can be chosen as any of the following –

• Last element
• First element
• Random element
• Median element

We will choose the last element as a pivot.

## Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot can be the last index element.

2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it . After this partitioning, the pivot is in its final position. This is called the partition operation.

3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

# Implementation of Quick Sort in JAVA

## Program for Quick Sort in Java

Let us have a look on the program below –

Run
```//Java Program for Merge Sort
class Main {
// this function display the array
public static void display(int[] arr, int size)
{
for(int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// main function of the program
public static void main(String[] args)
{
int[] a = {12, 11, 13, 5, 6, 7 };

int size = a.length;
display(a, size);

quickSort(a, 0, size - 1);
display(a, size);
}
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//Recursive function to apply quickSort
static void quickSort(int[] arr, int low, int high)
{
if (low < high)
{
/* indexPI is partitioning index, partition() function will
return index of partition */
int indexPI  = partition(arr, low, high);

quickSort(arr, low, indexPI  - 1);  //left partition
quickSort(arr, indexPI  + 1, high); //right partition
}
}
/* Partition function to do Partition
elements on the left side of pivot elements would be smaller than pivot
elements on the right side of pivot would be greater than the pivot
*/
static int partition(int[] arr, int low, int high)
{
// Pivot element selected as right most element in array each time.
int pivot = arr[high];
int swapIndex  = (low - 1);   //swapping index.

for (int j = low; j <= high- 1; j++)
{
//Check if current element is smaller than pivot element.
if (arr[j] < pivot)
{
swapIndex++;    //increment swapping index.
swap(arr, swapIndex, j);
}
}
// swap swapindex+ 1 and pivot index
// we assigned pivot = arr[high] is pivot index is high
swap(arr, swapIndex + 1, high);

return (swapIndex + 1);
}
}```

### Output

```12 11 13 5 6 7
5 6 7 11 12 13```
• This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are of Ο(n2), where n is the number of items.
• Quick sort is more advantageous than merge sort, as in merge sort we need a temporary array to merge the sorted arrays, and hence it is not fruitful than quick sort.