# Quick Sort Algorithm

May 19, 2019

This algorithm is very useful for large input. And, is quite efficient one. It has several implementation, and it is proved that for practical cases, it is better than Merge Sort, Heap Sort any many other algorithms. Although, its worst complexity is O(n^2).

This is again an implementation of of Divide and Conquer algorithms. In this algorithm, we first find a pivot element, put it in a position such that every element in left is less than or equal than this. And every element on right side is greater than equal than this number.

So, this pivot element divides the array into two parts. Then, natural recursive algorithm work on individual smaller arrays. Note: It is very important to choose correct pivot element. This algorithm works best when pivot element divides the array into almost equal halves. That is the reason, there are several implementations are available for selecting pivot element.

In a simple implementation, we simply choose the last element as pivot. Some algorithms choose a random pivot element.

## Quick Sort Algorithm

• First, we call partition on the array, where lies the main logic of putting the pivot element to correct position.
• Pivot element divides the array into two partitions.
• Now, runs the recursive method on the two partitions.
• Ultimately, partition sorts the sub-array.

See the code here:

``````public static int partition(int[] arr, int l, int r) {
int p = r;  //pivot

int sm = l;
for (int i=l; i<r; i++) {
if (arr[i] < arr[p]) {
ArrayUtils.swap(arr, i, sm);
sm++;
}
}
ArrayUtils.swap(arr, sm, p);
return sm;
}

public static void qsort(int[] arr, int l, int r) {
if (l < r) {
int p = partition(arr, l, r);

qsort(arr, l, p-1);
qsort(arr, p+1, r);
}
}``````

The main logic resides in partition() method. We just kept an index variable: sm which keeps track of all smaller number than our pivot element. And, finally swap our index sm and pivot element index.

## Key Points

• It does not use extra memory.
• Very efficient in sorting large number set.
• Practically best performer than merge sort, if implemented better for selecting pivot element.
• Performance is very good. Average complexity is O(n log n)
• Based on Divice and Conquer technique
• It works well in virtual memory environment

## Runtime complexity

The average runtime is O(n log n), but worst case is O(n^2)

## Similar Posts

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Heap Sort Algorithm

This is another very useful sorting algorithm based on Heap data structure. Read…

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

### Min Priority Queue Implementation with Heap Data structure

Min Priority Queue is a data structure which manage a list of keys(values). And…

### Insertion Sort Algorithm

Its a kind of incremental insertion technique, where the algorithm build up…

### Valid Anagrams - Leet Code Solution

Problem Statement Given two strings s and t , write a function to determine if t…

## Latest Posts

In this post, we will see some of the frequently used concepts/vocabulary in…

System design interview is pretty common these days, specially if you are having…

### Find the maximum sum of any continuous subarray of size K

Introduction You are given an array of integers with size N, and a number K…

### Graph Topological Sorting - Build System Order Example

Graph Topological Sorting This is a well known problem in graph world…

### Binary Tree - Level Order Traversal

Problem Statement Given a Binary tree, print out nodes in level order traversal…

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…