Quick Sort Algorithm - The Coding Shala

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

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala