Introduction to Quick Sort in Java
The following article, Quick Sort in Java, provides an outline for the quick sort algorithm in java. The Quick Sort Algorithm is one of the sorting algorithms which is efficient and similar to that of the merge sort algorithm. This is one of the prevalently used algorithms for real-time sorting purposes. The worst-case time complexity of this algorithm is O(n^2), the average-case time complexity is O(n log n), and the best-case time complexity is O(n log n).
The space complexity if O(n log n), where is n is the size of the input. The process of sorting involves the partitioning of input, recursive iterations and marking a pivotal element for each recursion. The type of sorting in this algorithm involves a comparison of adjacent elements in an iterative manner.
How Quick Sort Works in Java?
Quick Sort algorithm can be implemented in Java by forming a pseudo code with a sequence of steps designed and followed in an efficient manner.
- The main principle of the quick sort algorithm that it works is based on the divide and conquer approach and is also an efficient sorting algorithm.
- The input array is divided into sub-arrays, and the division is based on the pivot element, which is a central element. The sub-arrays on either side of the pivot element are the main areas where the sorting actually occurs.
- The central pivot element is the base to divide the array into two partitions where the left half of array elements are lesser than the pivot element, and the right half of array elements are greater than the pivot element.
- Before considering the pivot element, it can be anyone from the elements of an array. This is normally considered the middle one or the first one, or the last one for ease of understanding. The pivot element can be a random one from any of the array elements.
- In our example, the last element of an array is considered as a pivot element, where the partitioning of sub-arrays starts from the right end of the array.
- Finally, the pivot element will be in its actual sorted position after the completion of the sorting process, where the main process of sorting lies in the partition logic of the sorting algorithm.
- The efficiency of the algorithm depends on the size of the sub-arrays and how they are balanced. The more the sub-arrays are unbalanced, the more the time complexity will be, leading to worst-case complexity.
- The selection of pivot elements in a random manner results in the best time complexity in many cases instead of choosing a particular start, end or middle indexes as the pivot elements.
Examples to Implement Quick Sort in Java
The QuickSort algorithm has been implemented using Java programming language as below, and the output code has been displayed under the code.
- The code initially takes the input using the method quickSortAlgo() with the array, initial index and final index, i.e., length of the array as the arguments.
- After calling the quickSortAlgo() method, it checks if the initial index is less than the final index and then calls the arrayPartition() method to get the pivot element value.
- The partition element contains the logic of arranging the smaller and larger elements based on the element values around the pivot element.
- After getting the pivot element index after partition method execution, the quickSortAlgo() method is called by itself recursively until all the sub-arrays are partitioned and sorted completely.
- In the partition logic, the last element is assigned as a pivot element and the first element is compared with the pivot element, i.e. the last one where the elements are swapped based on whether they are smaller or greater.
- This process of recursion happens until all the elements of an array are partitioned and sorted, where the final result is a combined sorted array.
- The elements are swapped inside the for-loop iteration only in the case the element is lesser than or equal to the pivot element.
- After completing the iteration process, the last element is swapped, i.e. the pivot element value is moved to the left side so that the new partitions are made, and the same process repeats in the form of recursion, which results in series of sorting operations on different possible partitions as a formation of sub-arrays out of the given array elements.
- The below code can be run on any IDE, and the output can be verified by changing the array value in the main(). The main method is used just for the purpose of getting the output in the console. As a part of Java coding standards, the main method can be removed below, and an object can be created, and the below methods can be called by making them non-static.
Code Implementation of Quick Sort Algorithm in Java
Following is a code implementation:
Code:
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}Output:
Conclusion
The Quick Sort Algorithm is efficient but not much stable as compared to other sorting techniques. The efficiency of quick sort algorithms comes down in the case of a greater number of repeated elements which is a drawback. The space complexity is optimized in this quick sort algorithm.
Recommended Articles
This is a guide to Quick Sort in Java. Here we discuss how quick sort works in Java, along with an example and implementation of code. You can also go through our other suggested articles to learn more –
