In this article, we will explore the implementation of quick sort in Java. We will discuss the logical steps involved in the algorithm, provide a sample Java code, analyze its time and space complexity, explore its applications, and conclude with the advantages of using quick sort in Java.
Java Code
class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 9, 1, 7};
System.out.println("Original Array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.print("\n");
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted Array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public 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
Original Array:
5 3 9 1 7
Sorted Array:
1 3 5 7 9 Logical Steps for Quick Sort in Java
- Select a pivot element from the array.
- Partition the array into two subarrays, with elements less than the pivot on the left and elements greater than the pivot on the right.
- Recursively apply steps 1 and 2 to the subarrays until the entire array is sorted.
Time Complexity
The average time complexity of quick sort is O(n log n), making it one of the fastest sorting algorithms. However, in the worst-case scenario, where the array is already sorted or contains mostly equal elements, the time complexity can be O(n^2).
Space Complexity
The space complexity of quick sort is O(log n) on average, as it uses the stack for recursion. In the worst case, it can be O(n) if the recursion depth is maximum.
Applications
- Quick sort is extensively used in various programming languages and libraries for sorting large datasets efficiently.
- It is widely used in database systems for indexing and searching.
- Quick sort is utilized in various data processing applications, such as data deduplication and data analytics.
Conclusion: Quick Sort in Java
Quick sort is a powerful sorting algorithm that provides efficient and fast sorting of arrays. Its versatility, speed, and effectiveness make it a popular choice for sorting large datasets in Java and other programming languages.
Understanding and implementing quick sort in Java can greatly enhance your ability to efficiently sort and manipulate arrays, improving the performance of various applications and algorithms.
Related Links: