Quick Sort Algorithm - The Coding Shala

Quick Sort Algorithm - The Coding Shala

January 27, 2021

Last Updated: 27-Jan-2021

Home >> Algorithms >> Quick Sort Algorithm

In this post, we will learn what is Quick Sort Algorithm and will write a Java program for Quick Sort.

Quick Sort Algorithm

Quick Sort is one of the most efficient sorting algorithms. If effectively implemented quick sort algorithm is significantly faster than any of the common sorting algorithms. Like Merge Sort, Quicksort is also a classic example of the divide-and-conquer approach.

Working of Quick Sort Algorithm

In a quick sort algorithm, we follow the divide and conquer approach. The following are the steps used in quicksort:

step 1. First, we select a value from the list, called pivot value and it divides the list into two sublists. One sublist contains all the values that are less than the pivot value, another sublist contains the values that are greater than or equal to the pivot value. This process is also called partitioning. we can choose the first/last element in the list as the pivot or can randomly pick an element from the list.
Step 2. We repeat this partitioning process to reduce the list into two smaller sublists. We then recursively sort the two sublists.
Step 3. After the partitioning process, we can simply concatenate the two sorted sublists.

Here is an example that explains the quick sort algorithm:

Quick Sort Algorithm Example - The Coding Shala

Time Complexity of Quick Sort Algorithm

The average time complexity of quicksort is O(N log N), where N is the length of the list.

The time complexity of quick sort depends on the pivot value and it varies from O(N log N) in the best case and O(N^2) in the worst case.

Quick Sort Algorithm Java Program

The following is the Java Program of Quick Sort Algorithm.

Java Program:

import java.util.Arrays;

//quick sort
//the coding shala

class Main{
	
	public static void quick_sort(int[] input, int start, int end) {
		//do partition is start less than end
		if(start < end) {
			int pivot = partition(input, start, end);
			quick_sort(input, start, pivot-1);
			quick_sort(input, pivot+1, end);
		}
	}
	
	public static int partition(int[] input, int start, int end) {
		//we are selecting pivot as last element
		int pivot = input[end];
		//first sublist every element must be less than pivot
		//we will start loop form start to less then end
		//than will exchange with pivot
		
		int st = start;

                //move if element is less then pivot to get in acending order
		//move if element is greater than to get list in decending order
		for(int j = start; j< end; j++) {
			if(input[j]<=pivot) {
				int tmp = input[st];
				input[st] = input[j];
				input[j] = tmp;
				st++;
			}
		}
		
		//now exchange pivot
		int tmp = input[st];
		input[st] = pivot;
		input[end] = tmp;
		return st;
	}
	
	public static void main(String[] args) {
		int[] input = {1,5,3,2,8,7,6,4};
		int len = input.length;
		quick_sort(input,0, len-1);
		for(int i=0;i<input.length;i++) {
			System.out.print(input[i]+" ");
		}
	}
}

Other Posts You May Like

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments