# Quicksort java

Let’s learn quicksort java.

## Quicksort java

Basically quicksort is a divide and conquer algorithm. Quicksort is one of the widely used sorting algorithm. Because it is used to sort large datasets or lists.

quick sort in java implementation

Below are steps for quicksort algorithm java.

Given an array of numbers we want to sort them in an ascending order and that’s what quicksort does. So here we have an array of nine elements. First we need to know one term, that is, pivot.

Pivot is middle index element that we are going to compare with every other item. Then elements are divided into two parts. One with element less than pivot and other greater than pivot.

We are going to move items that are less than or equal to the pivot to the left of the pivot and items that are greater than or equal to the pivot to the right of the pivot.

Then we have left partition and a right partition. Finally quicksort recursively sorts the above mentioned two partitions.

Quicksort uses recursive method or recursion (quicksort java recursive) in which method calls itself. Because it continues to call quicksort on a smaller and smaller subset of items.

This algorithm don’t need another array since sorting takes place in the same array. It’s very efficient for very large datasets.

quick sort (example) java recursive

Let’s see quick sort program in java.

```// quicksort java code
import java.util.Arrays;
public class QuickSortInJava
{
int partition(int[] arrNumbers, int low, int high)
{
int pivot = arrNumbers[high];
// smaller element index
int a = (low - 1);
for(int b = low; b < high; b++)
{
// if current element is smaller than the pivot
if(arrNumbers[b] < pivot)
{
a++;
// swap arrNumbers[a] and arrNumbers[b]
int temp = arrNumbers[a];
arrNumbers[a] = arrNumbers[b];
arrNumbers[b] = temp;
}
}
// swap arrNumbers[a + 1] and arrNumbers[high] or pivot
int temp = arrNumbers[a + 1];
arrNumbers[a + 1] = arrNumbers[high];
arrNumbers[high] = temp;
return a + 1;
}
void sort(int[] arrNumbers, int low, int high)
{
if (low < high)
{
int p = partition(arrNumbers, low, high);
/* recursive sort elements before
partition and after partition */
sort(arrNumbers, low, p - 1);
sort(arrNumbers, p + 1, high);
}
}
static void displayArray(int[] arrNumbers)
{
int s = arrNumbers.length;
for(int a = 0; a < s; ++a)
System.out.print(arrNumbers[a] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] arrNumbers = {59, 74, 85, 67, 56, 29, 68, 34};
int s = arrNumbers.length;
QuickSortInJava obj = new QuickSortInJava();
obj.sort(arrNumbers, 0, s - 1);
System.out.println("After sorting array: ");
displayArray(arrNumbers);
}
}

```

Output:

After sorting array:
29 34 56 59 67 68 74 85

quick sort has space complexity of O(log n).

Quicksort has an average O(n log n) of time complexity.

Quicksort has worst case of O(n²).

quick sort in java user input

Now let’s learn to implement quicksort in java where user enters numbers as input.

```import java.io.BufferedReader;
import java.util.Arrays;
import java.util.Random;
public class QuickSortUserInput
{
static int partition(int[] arrNumbers, int low, int high)
{
int b, temp, a = low + 1;
Random rand = new Random();
int r = rand.nextInt(high - low) + low;
temp = arrNumbers[low];
arrNumbers[low] = arrNumbers[r];
arrNumbers[r] = temp;
for(b = low + 1; b <= high; b++)
{
if(arrNumbers[b] <= arrNumbers[low] && b != a)
{
temp = arrNumbers[b];
arrNumbers[b] = arrNumbers[a];
arrNumbers[a++] = temp;
}
else if(arrNumbers[b] <= arrNumbers[low])
{
a++;
}
}
temp = arrNumbers[a - 1];
arrNumbers[a - 1] = arrNumbers[low];
arrNumbers[low] = temp;
return a - 1;
}
// quick sort function
static void quickSort(int[] arrNumbers, int low, int high)
{
if(low < high)
{
int middle = partition(arrNumbers, low, high);
quickSort(arrNumbers, low, middle - 1);
quickSort(arrNumbers, middle + 1, high);
}
}
public static void main(String[] args)
{
int size;
System.out.println("Please enter size of the array: ");
try
{
}
catch(Exception ex)
{
System.out.println("Sorry!! Invalid Input");
return;
}
int[] arrNumbers = new int[size];
for(int a = 0; a < arrNumbers.length; a++)
{
try
{
}
catch(Exception ex)
{
System.out.println("Error");
}
}
System.out.println("Before sorting array: ");
System.out.println(Arrays.toString(arrNumbers));
quickSort(arrNumbers, 0, arrNumbers.length - 1);
System.out.println("After sorting array: ");
System.out.println(Arrays.toString(arrNumbers));
}
}

```

Output:

Please enter size of the array:
6