What is a Quick Sort Algorithm in Data Structures? | Data Structures Tutorial

In this article, you will learn about the quick sort algorithm in brief.

It is a sorting algorithm that is based on the divide and conquers approach where 

1. An array is divided into subarrays by selecting a pivot element(an element selected from the array). While creating the sub-arrays, the pivot element should be placed in such a way that elements smaller than the pivot are kept on the left side and elements greater than the pivot is on the right side of the pivot. 
2. The left and right sub-arrays are also divided through the same approach. This process continues until each subarray contains a single element. 
3. Now the elements are sorted. Finally, elements are combined to form a sorted array.

Quick Sort Working

1. Select the Pivot Element: There are multiple variations of quicksort where the pivot element is selected from multiple positions. Now, we will be choosing the rightmost element of the array as the pivot item. 
2. Rearrange the array: Now the elements of the array are rearranged so that items less than the pivot are put on the left and the elements greater than the pivot are placed on the right.
1. A pointer is pointed at the pivot element. The pivot item is compared with the elements beginning from the initial position.
2. If the value of the element is greater than the pivot, a second pointer is set for that element.
3. The value of the pivot element is compared with other elements. If an element less than the pivot element is reached, the value is swapped with the greater element.
4. The steps are repeated to set the next greater element as the second pointer. Swap the elements with the smallest element.
5. It will go on until reaching the second last element.
6. Now, the pivot element is swapped with the second pointer.
3. Divide Subarrays: The pivot elements are again chosen for the left and the right sub-parts. Now again repeat step 2.

Complexity

Time complexity

The best case complexity is O(n*log n), the average case complexity is O(n*log n), and the worst case complexity is O(n2).

Space complexity is O(log n)

Applications of Quick Sort

• Used in figuring out the space complexity.
• Used in figuring out the time complexity
• Used in the programming language for recursion