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
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.

It's good to share...Share on FacebookTweet about this on TwitterShare on LinkedInPin on PinterestShare on Google+Email this to someone

4 Thoughts on “Quick Sort Algorithm”

Leave a Reply

Your email address will not be published. Required fields are marked *