# QuickSort in JAVA

In this tutorial, we are going to learn how to perform QuickSort in Java.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

‘QuickSort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,9,4,7}

1. Fix one particular element of the array (this element is termed pivot)
let the last element 7 be the pivot
2. Partition all the elements of the array, lesser than the pivot, to the left (or right) and all the elements of the array, greater than the pivot, to the right (or left); to sort in ascending (or descending) order
all elements lesser than 7 go to the left-> {1,4}
all elements greater than 7 go to the right -> {9}
so array -> {{1,4},7,{9}}
3. Treat all the elements to the left as a new array and start from step 1, unless only one element remains
let the last element in {1,4} be the pivot
then, all elements lesser than 4 go to the left -> {1}
there are no elements greater than 4 to go to the right
so array -> {{{1},4},7,{9}}
4. Treat all the elements to the right as a new array and start from step 1, unless only one element remains
9 is the only element present in {9}, so no further action
so array -> {{{1},4},7,{9}}
Hence, the sorted array is -> {1,4,7,9}

## Java code for QuickSort Sorting

```import java.util.Scanner;
public class QuickSort
{
void inputArray(int array[],int length)
{
Scanner scan=new Scanner(System.in);
System.out.print("Input "+length+" (integer) elements: ");
//note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
for(length--;length>=0;length--){
array[length]=scan.nextInt();
}
}
void printArray(int array[],int length)
{
System.out.print("The elements of the given array are: ");
for(int i=0;i<length;i++)System.out.print(array[i]+" ");
}
void swap(int array[],int i,int j)//this function swaps the values present at indices i and k in array[]
{
int temporary = array[i];
array[i]=array[j];
array[j]=temporary;
}
//here onwards, 'lower' indicates the first index of the passed array and 'upper' indicates last index of the passed array
int partition (int array[], int lower, int upper)//this function partitions the array, treating the last element as the pivot
{
int i = (lower - 1);  //index of smaller element
for (int j = lower; j < upper; j++)
{
if (array[j] <= array[upper])//THIS CONDITION SORTS IN ASCENDING ORDER
{
i++; // incrementing index of smaller element
swap(array,i,j);//passing the addresses of the array elements for swapping
}
}
swap(array,i+1,upper);
//swap(&array[i + 1], &array[upper]);//finally, swapping the pivot and the element in the position at which pivot is supposed to be
return (i + 1);//returning the position that the pivot would take in the sorted array
}
void quickSort(int array[], int lower, int upper)
{
if (lower < upper)//this condition checks whether the array contains more than one element
{
int pivotIndex = partition(array, lower, upper);//getting the index of the pivot after partition of the array
quickSort(array, lower, pivotIndex - 1);//sorting elements before the pivot
quickSort(array, pivotIndex + 1, upper);//sorting elements after the pivot
}
}
public static void main(String args[])
{
QuickSort ob = new QuickSort();
int array[] = new int;
ob.inputArray(array,4);
ob.quickSort(array,0,4-1);//passing 4-1 because array-index-counting starts from 0
ob.printArray(array,4);
}
}//class ends```

#### Output:

```Input 4 (integer) elements: 1 9 4 7
The elements of the given array are: 1 4 7 9```

#### Summary:

• an object ‘ob’ of the class is created to call the required functions
• an array ‘array[]’ is initialized with length 4
• ob.inputArray(int[],int) is called to take input integer elements from the user and store them in the array
• ob.quickSort(int[],int,int) is called to sort the elements of the array with the algorithm explained above
• ob.printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

• the value ‘4’ can be changed to any other value in order to get the desired array-length
• since (in JAVA) arrays are passed by reference, therefore the changes made in quickSort(int[],int,int) and partition(int[],int,int) stay permanently
• to sort in descending order, just change the sign from ‘<=’ to ‘>‘ in the logical condition inside the for loop of partition(int[],int,int)