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