Quick Sort in Data Structures - Infovistar

Quick Sort

Quick sort is the fastest internal sorting algorithm with the time complexity of O (n log n). It is a highly efficient algorithm.

This algorithm uses the divide and conquer technique. A divide and conquer strategy breaks down algorithms into smaller subproblems, solves each subproblem, and then combines the results to solve the original problem.

• Divide: In Divide, select a pivot element. After that, divide the array into two sub-arrays, with each element in the left sub-array being smaller than or equal to the pivot element and each element in the right sub-array being larger.
• Conquer: Sort two subarrays recursively with Quicksort.
• Combine: Combine the sorted arrays.

Quicksort picks one element as the pivot, and then partitions the array around the pivot element.

The quick sort method divides a large array into two arrays, the first containing values that are smaller than the pivot, and the second containing values that are larger than the pivot.

Following that, left and right subarrays are also partitioned using the same method. This continues until the sub-array contains a single element.

Selecting a pivot

A good pivot is essential to the fast implementation of quicksort. However, it is common to determine a good pivot.

• The pivot can be chosen randomly from the array, i.e. select the random pivot.
• The pivot element can either be the rightmost element or the leftmost element of an array.
• Choose the median element as the pivot.

Time Complexity

Case Time Complexity
Best Case O(n log n)
Average Case O(n log (n)2)
Worst Case O(n2)
• Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
• Average Case O(n log (n)2): The array elements are in a jumbled order that is not properly ascending and descending.
• Worst Case O(n2): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

 Space Complexity O(n log n) Stable No
• The space complexity of quick sort is `O (n log n)`.