QuickSort is a divide and conquer algorithm. In the divide and conquer algorithm design paradigm, we recursively divide the problem into subproblems, then solve the subproblems, and finally combine the solutions to find the final results.
One thing to remember when dividing a problem into subproblems is that the structure of the subproblem will not change like the original problem.
The algorithm has three steps:
- Division: decompose the problem into sub problems
- Conquer: solve subproblems recursively
- Merge: merge solutions for final results
There are many algorithms based on divide and conquer paradigm. Quick sort and merge sort are one of them.
Although QuickSort has a worst-case time complexity of O (n2), which is higher than many other sorting algorithms (such as "merge sort" and "heap sort"), QuickSort is faster in practice because its internal loop can efficiently realize real data on most architectures and in most architectures.
Let's talk about the implementation of quick sorting algorithm. The quick sort algorithm uses pivot elements and partitions the array around the pivot elements. Quicksot comes in many variants, depending on how you select pivot elements. There are several ways to select pivot elements:
- Select the first element
- Select the last element
- Select a random element
- Pick median element
The next important thing to understand is the partition() function in the Quick sort algorithm. The partitioning function takes a pivot element, places it on the right, moves all elements smaller than the pivot element to the left, and moves all elements larger than the pivot element to the right. Quicksort takes linear time.
Then, the array is divided into two parts from the pivoted elements (that is, elements smaller than the pivoted elements and elements larger than the pivoted elements), and the Quicksort algorithm is used to sort the two arrays recursively.
Now we understand how the Quicksort algorithm works. Let's learn how to implement quicksort algorithm in Java.
Quick sort function:
/* Quicksort Function needs to sort the array with the lowest and highest indexes */
void sort(int arr[], int lowIndex, int highIndex) { // Until lowIndex = highIndex if (lowIndex < highIndex) { // partitioning of the array int p = partition(arr, lowIndex, highIndex); // Recursively sort elements before & after partition sort(arr, lowIndex, p - 1); sort(arr, p + 1, highIndex); } }
Now let's take a look at the partitioning code to see how it works.
Partition code
In the partition code, we select the last element as the pivot element. We iterate through the entire array (that is, in our example, using the variable j). We trace the last smallest element in the array (that is, in this case, the variable I). If any element smaller than the pivot is found, the movement of the current element a [j] and arr [i] will be exchanged, otherwise we continue to traverse.
int partition(int arr[], int lowIndex, int highIndex) { // Making the last element as pivot int pivot = arr[highIndex]; // Using i to keep track of smaller elements from pivot int i = (lowIndex - 1); for (int j = lowIndex; j < highIndex; j++) { // If current element is smaller than or equal to pivot if (arr[j] <= pivot) { i++; // increment i // swap ith element with jth element int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // moving pivot at its correct position int temp = arr[i + 1]; arr[i + 1] = arr[highIndex]; arr[highIndex] = temp; return i + 1; }
Now that you know about Quicksort and partitioning, let's take a quick look at the complete code
QuickSort Java code
import java.util.Arrays; class QuickSortDemo { // Partition Method int partition(int arr[], int lowIndex, int highIndex) { int pivot = arr[highIndex]; System.out.println(pivot); int i = (lowIndex - 1); for (int j = lowIndex; j < highIndex; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } System.out.println(Arrays.toString(arr)); } int temp = arr[i + 1]; arr[i + 1] = arr[highIndex]; arr[highIndex] = temp; return i + 1; } void sort(int arr[], int lowIndex, int highIndex) { if (lowIndex < highIndex) { int pi = partition(arr, lowIndex, highIndex); sort(arr, lowIndex, pi - 1); sort(arr, pi + 1, highIndex); } } static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = { 15, 85, 35, 95, 45, 65, 75 }; int n = arr.length; QuickSortDemo ob = new QuickSortDemo(); ob.sort(arr, 0, n - 1); System.out.println("sorted array"); printArray(arr); } }
Output:
75
[15, 85, 35, 95, 45, 65, 75]
[15, 85, 35, 95, 45, 65, 75]
[15, 35, 85, 95, 45, 65, 75]
[15, 35, 85, 95, 45, 65, 75]
[15, 35, 45, 95, 85, 65, 75]
[15, 35, 45, 65, 85, 95, 75]
65
[15, 35, 45, 65, 75, 95, 85]
[15, 35, 45, 65, 75, 95, 85]
[15, 35, 45, 65, 75, 95, 85]
45
[15, 35, 45, 65, 75, 95, 85]
[15, 35, 45, 65, 75, 95, 85]
35
[15, 35, 45, 65, 75, 95, 85]
85
[15, 35, 45, 65, 75, 95, 85]
sorted array
15 35 45 65 75 85 95