Hello! In this blog tutorial, we will learn how to implement the Quick Sort algorithm in Java. Quick Sort has an average time complexity of O(n log n) and a worst-case time complexity of O(n²), but it is known to be a very efficient sorting algorithm in many cases. By understanding this, you can improve your problem-solving skills in coding tests.
1. What is Quick Sort?
Quick Sort is a sorting algorithm that uses the ‘divide and conquer’ method. This algorithm works as follows:
- Select one element from the array to be sorted as the ‘pivot’.
- Divide the remaining elements of the array into two parts based on the pivot. The left part consists of elements smaller than the pivot, and the right part consists of elements greater than the pivot.
- Recursively perform Quick Sort on the left and right parts.
This process results in a final sorted array.
2. Problem Definition
Problem: Sort the given integer array using the Quick Sort algorithm.
Input
- One-dimensional integer array arr (0 ≤ arr.length ≤ 106, -109 ≤ arr[i] ≤ 109)
Output
- Sorted one-dimensional integer array
3. Quick Sort Algorithm Implementation
Now, let’s implement the Quick Sort algorithm in Java. Below is the Java code for Quick Sort:
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Sort the left part
quickSort(arr, pi + 1, high); // Sort the right part
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Select the pivot (the last element in this implementation)
int i = (low - 1); // Index of smaller elements
for (int j = low; j < high; j++) {
// If the current element is less than or equal to the pivot
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Move the pivot to its correct position
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return the index of the pivot
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
System.out.println("Original array: " + Arrays.toString(arr));
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
4. Code Explanation
4.1. Main Method
The main method defines the array to be sorted and outputs both the original and sorted arrays. It calls the quickSort method to perform Quick Sort.
4.2. quickSort Method
The quickSort method sorts the array through recursive calls. low and high represent the indices of the array, and after dividing the array into two parts based on the pivot, quickSort is called again on each part.
4.3. Partition Method
The partition method is responsible for dividing the array based on the pivot. Elements smaller than the pivot are moved to the left, and elements greater than the pivot are moved to the right. Finally, the pivot is moved to its correct position to complete the sorted array.
5. Time Complexity
Quick Sort has an average time complexity of O(n log n) and a worst-case time complexity of O(n²). The worst case can occur when the pivot is chosen from an already sorted array. However, several strategies, such as choosing a random pivot or the median, can help avoid the worst case.
6. Conclusion
In this article, we learned how to implement the Quick Sort algorithm in Java. Quick Sort is a very useful sorting algorithm, and it is frequently featured in coding tests, so it is highly recommended to familiarize yourself with it. I hope studying various sorting algorithms helps improve your problem-solving skills. In the next post, we will cover other algorithms. Thank you for reading!