###### Quick Sort Algorithm

Quick sort (sometimes called partition-exchange sort) is an efficient sorting algorithm.

It is a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort.

Quick sort is a divide and conquer algorithm. Quick sort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quick sort can then recursively sort the sub-arrays.

The steps are as below.

(1) Pick an element, called a pivot, from the array.

(2) Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

(3) Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

There are many versions of this algorithm to select pivot, Here we are taking middle of the list as pivot element. Quick Sort Explanation
###### Performance
• Worst-case performance :- O(n2)
• Best-case performance :- O(n log n) (simple partition) or O(n) (three-way partition and equal keys)
• Average performance :- O(n log n)
• Worst-case space complexity :- O(n) auxiliary (naive), O(log n) auxiliary
###### Java Program of Quick Sort Algorithm

Output

Input Array before Quick Sort. 25 10 30 15 20 10 5 Sorted Array after Quick Sort. 5 10 10 15 20 25 30

Some theory part of this article uses material from the Wikipedia article “Quick Sort”, which is released under the CC BY-SA 3.0.

## 4 Thoughts on “Quick Sort Algorithm”

• SagarKapasi099 says:

Well, I’m Having A Doubt, As To Why At Line 46 And 48 If Conditions Have Been Specified

• SagarKapasi099 says:

Great Explaination Though

• admin says:

Glad to know that you like the article.

• admin says:

Those if conditions are to decide which value to be passes in next recursive call…
Beauty of recursion…
Happy learning 🙂