Java Program to Implement Quick Sort Algorithm
What is Quicksort in java.
The quicksort sorting algorithm divides an unsorted list into smaller sublists, which are then repeatedly sorted until the full list is sorted. The list is split into two sublists: elements less than the pivot and elements greater than the pivot when it selects a “pivot” element. The two sublists are then sorted recursively with the pivot put in its last position in the sorted list.
- The final sorted array is obtained by concatenating the left sub-array, pivot, and right sub-array.
- This algorithm has a time complexity of O(n log n) in the average and best case, and O(n^2) in the worst case.
- Quicksort is widely used due to its efficiency and simplicity.
To know more about Quicksort Algorithm in java read the complete article.
How to implement QuickSort in Java
Quicksort can be implemented in Java as follows:
- Define a quickSort method that takes in the array to be sorted, the start index, and the end index.
- In the quickSort method, select a pivot element from the array.
- Partition the array into two sub-arrays, one containing elements less than the pivot and the other containing elements greater than the pivot.
- Recursively sort the sub-arrays by calling the quickSort method on each of them.
- Concatenate the two sub-arrays and the pivot element to obtain the final sorted array.
Choosing the Optimal Pivot in Quicksort algorithm in java :
Choosing the optimal pivot in the Quicksort algorithm can greatly impact the performance of the algorithm. There are several strategies for choosing the pivot, including:
First Element: Selecting the first element of the array as the pivot. This is the simplest strategy, but it can lead to poor performance if the array is already sorted or nearly sorted.
Last Element: Selecting the last element of the array as the pivot. This strategy is often used in practice because it’s simple and efficient in most cases.
Median Element: Selecting the median element of the array as the pivot. This strategy can lead to good performance, as the median is likely to be a better representative of the elements in the array.
Random Element: Selecting a random element of the array as the pivot. This strategy can provide good performance, as it reduces the chances of the worst-case scenario occurring.
Ultimately, the choice of pivot will depend on the specifics of the problem and the data being sorted. It’s important to choose a pivot strategy that’s appropriate for the data and the problem being solved.
Let’s look at a Java program where the implementation of Quicksort Algorithm on java is used to perform an operation.
Example: Implementation of Quicksort Algorithms in java
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length-1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex-1);
quickSort(arr, pivotIndex+1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low-1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
Output
Sorted array: [1, 5, 7, 8, 9, 10]
Example 2 : Java Quicksort Algorithm Method
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
quickSort(input,0,input.length-1);
System.out.println("Sorted Array: " + Arrays.toString(input));
}
private static void quickSort(int[] input, int start, int end) {
if (start < end) {
int partitionIndex = partition(input, start, end);
quickSort(input, start, partitionIndex-1);
quickSort(input, partitionIndex+1, end);
}
}
private static int partition(int[] input, int start, int end) {
int pivot = input[end];
int i = start-1;
for (int j = start; j < end; j++) {
if (input[j] <= pivot) {
i++;
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
int temp = input[i + 1];
input[i + 1] = input[end];
input[end] = temp;
return i + 1;
}
}
Output
Sorted Array: [2, 2, 12, 20, 24, 45, 53, 56, 56, 75, 99]
Example 3: how to use the object clone property:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] input = {12,6,18,17,4,95,2,73,90,34,13};
quickSort(input,0,input.length-1);
System.out.println("Sorted Array: " + Arrays.toString(input));
}
private static void quickSort(int[] input, int start, int end) {
if (start < end) {
int partitionIndex = partition(input, start, end);
quickSort(input, start, partitionIndex-1);
quickSort(input, partitionIndex+1, end);
}
}
private static int partition(int[] input, int start, int end) {
int pivot = input[end];
int i = start-1;
for (int j = start; j < end; j++) {
if (input[j] <= pivot) {
i++;
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
int temp = input[i + 1];
input[i + 1] = input[end];
input[end] = temp;
return i + 1;
}
}
Output
Sorted Array: [2, 4, 6, 12, 13, 17, 18, 34, 73, 90, 95]
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment