Quicksort program in Java
In this post, you will learn about the Quick Sort and how to write a quick sort program using the Java programming language.
Quick sort is widely used sorting algorithm, it is developed by C.A.R.
In quick sort, it first selects one element called a pivot. After that, it rearranges the elements in the array in such a way that all the elements less than the pivot element are appearing before the pivot and all the elements greater than the pivot are appearing after the pivot. After this, partitioning the pivot is in the final position.
Quick sort is the fastest algorithm and is the best choice. It is faster than other algorithms like bubble sort, selection sort, and insertion sort. But this can be complex on the flip side.
Quick Sort Example
These are the quick sorting techniques.
We choose the first element as a pivot. So set loc at 0 index, left at 0 index and right at 5th index.
Now scan from right to left until a[loc] < a[right], then decrease the value of right.
Since a[loc] > a[right], interchange the two values and set loc = right.
Now scan from left to right until a[loc] > a[left], then increment the value of left.
Since a[loc] < a[left], interchange the values and set loc = left.
Since from right to left, since a[loc] < a[right], decrease the value of right.
Start scanning from left to right. Since a[loc] > a[left], increment the value of left.
Since a[loc] > a[right], interchange the two values and set loc = right.
Complexity of Quick sort
Suppose n is the number of elements in an array.
Best Time Complexity - O(n log(n))
Worst Time Complexity - O(n2)
Quick sort program in Java
import java.util.Arrays;
class Quicksort {
static int partition(int array[], int low, int high) {
//Making the last element as pivot
int pivot = array[high];
// index of smaller element
int i = (low - 1);
// traverse through all elements
// compare each element with pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
//swap ith element with jth element
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// moving pivot at its correct position
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return (i + 1);
}
// Sorting Method
static void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
}
// Main class
class Main {
public static void main(String args[]) {
int[] arr = { 98, 43, 29, 54, 89, 71};
System.out.println("Unsorted Array: ");
System.out.println(Arrays.toString(arr));
int size = arr.length;
// calling quicksort()
Quicksort.quickSort(arr, 0, size - 1);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(arr));
}
}
Output of the above code:
Unsorted Array:
[98, 43, 29, 54, 89, 71]
Sorted Array in Ascending Order:
[29, 43, 54, 71, 89, 98]
Related Articles
Sort array in ascending order JavaAutomorphic number in Java
Pascal triangle program in Java
Factorial using recursion in java
Java random number between 1 and 10
Palindrome program in Java
Floyd triangle in Java
Pyramid pattern programs in Java
Star pattern programs in Java
Number pattern programs in Java
Java program to find area of rectangle
Matrix multiplication in Java
Electricity bill program in Java
Java program to find area of triangle
Area of circle program in Java
Remove duplicate elements from array in Java
Capitalize first letter of each word Java
Convert binary to decimal in Java
Convert decimal to binary in Java
Convert decimal to octal in Java
Convert decimal to hexadecimal in Java
Simple interest program in Java