Java Program to Implement Quick Sort in Ascending Order

Java Program to Implement Quick Sort in Ascending Order example for beginners programming language written in Java.

It works by picking a ‘pivot’ element from the array and partitioning the remaining elements into two subarrays based on whether they are  greater or less than the pivot.

Quicksort in Java

Quicksort is a sorting algorithm that uses the divide-and-conquer concept to sort data.

It has an average complexity of O(n log n) and is one of the most popular sorting algorithms, especially for large data sets.

Why do the Java uses Quick sort

Quicksort program using pivot in java has added cost from the recursive function calls, insertion sort is faster for small n.

Insertion sort is also more stable and uses less memory than.

Quicksort has a better locality of reference than merge sort, which means that quicksort accesses are usually faster than the corresponding merge sort accesses.

Due to the overhead of merging, quicksort uses worst-case O(log n) memory, whereas merge sort requires O(n) memory.

Fastest Sorting Algorithm in Quick Sort Java Example

Quicksort has an O(n logn) time complexity in the best and average case scenarios, and O(n2) in the worst case.

Quicksort is often regarded the “fastest” sorting algorithm because it has the upper hand in the average situations for most inputs.

Fastest Sorting Method in Java

Radix sort:0.220s. Quicksort: 0.247s. Shell sort: 0.250s. Merge sort: 0.435s.

Insertion sort vs Quick Sort in Java

Quick Sort has added cost from the recursive function calls, insertion sort is faster for small n.

Insertion sort is also more stable and uses less memory than Quick sort.

Starting with the second value in the list, an insertion sort compares values one by one.

No changes are made if this value is greater than the value to the left of it.

Otherwise, this value is repeatedly shifted to the left until it encounters a value less than it.

The sorting procedure is then repeated with the next value.

Advantages of Quick Sort

It’s in place since it just requires a modest auxiliary stack. Sorting n things takes only n (log n) seconds. The inner loop is extremely short.

import java.util.Arrays;
class Main 
{
int a(int array[], int low, int high)
{
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) 
{
if (array[j] <= pivot)
{
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) 
{
int pi = a(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
public static void main(String args[]) 
{
int[] data = { 56,787,343,456,987,111};
int size = data.length;
Main qs = new Main();
qs.quickSort(data, 0, size - 1);
System.out.println("After sorting");
System.out.println(Arrays.toString(data));
}
}

Output:

After sorting           
[56, 111, 343, 456, 787, 987]