Updated March 24, 2023
Introduction to Quick Sort in Data Structure
Quick Sort in a data structure is a method to sort the list of elements. It uses the divide and conquer approach for this that means the array of elements are divided into 2 parts, and then further quick sort algorithm is applied to these 2 parts. This division of array takes place using a pivot point. The position of a pivot is selected such that the elements on the left of the pivot are less than the pivot element and also the element on the right is greater than the pivot element. This partitioning aims to obtain the sorted array in linear running time.
Algorithm for Quick Sort in Data Structure
Any of the following methods can choose a pivot:
- Last element of the array
- The first element of the array
- Any random element is picked.
- Median is picked as a pivot.
Quick Sort uses a function partition to find the partitioning point for an array, and Quick Sort is further called for 2 sub-arrays. This partition function uses an assumption to take the last element of the array as a pivot.
Algorithm for Quick Sort:
partition (myarr[], left, right)
{
pivot = myarr[right];
i = (left - 1)
for (j = left; j <= right- 1; j++)
{
if (pivot > myarr[j] )
{
i++;
swap myarr[i] and myarr[j]
}
}
swap myarr[i + 1] and myarr[right])
return (i + 1)
}
quickSort(myarr[], left, right)
{
if (left < right)
{
pi = partition(myarr, left, right);
quickSort(myarr, left, pi - 1);
quickSort(myarr, pi + 1, right);
}
}
Explanation: In the above algorithm, there is pseudocode for partition function used to find the partition element of the array followed by pseudocode for quicksort. Quick Sort algorithm calls the partition function to calculate the partitioning point. Quick Sort is a tail-recursive, in-place algorithm that makes it suitable for use in case of arrays of a large number of elements.
Examples to Implement Quicksort in Data Structure
Quick Sort can be implemented using 2 below scenarios which are as follows:
1. Recursive version of Quick Sort
Here we will see the recursive version of quicksort.
Code:
def partition(mymyarr,left,right):
i = ( left-1 )
pivot = mymyarr[right]
for j in range(left , right):
if myarr[j] <= pivot:
i = i+1
myarr[i],myarr[j] = myarr[j],myarr[i]
myarr[i+1],myarr[right] = myarr[right],myarr[i+1]
return ( i+1 )
def qSort(myarr,left,right):
if left < right:
pi = partition(myarr,left,right)
qSort(myarr, left, pi-1)
qSort(myarr, pi+1, right)
myarr = [12,56,23,767,3,88,3,56,5]
n = len(myarr)
qSort(myarr,0,n-1)
print ("After Sorting myarray is:")
for i in range(n):
print ("%d" %myarr[i])
Output:
Code Explanation: The above program is for the recursive Quick Sort approach where myarr is defined to be sorted, and 0th element, i.e. 12 is considered to be starting index and n-1th element, i.e. 5 is the end index. A partition function is called to find the partitioning element. Here we are considering the pivot element to be the last element and index of a smaller element less than the left of the array being passed as an argument. Then each element is compared with pivot and in case element smaller than pivot is found I get incremented and swapping of an element occurs. And when no element is left to be swapped, all elements in the left are lesser than pivot and elements on the right are greater than the pivot.
Further quicksort algorithm is called for this subarray, and this way algorithm keeps on dividing the array and sort the elements.
Complexity
Here are 3 types of complexity which are explained below:
1. Best Case: This case occurs when partition elements happen to be always the middle element of the array. In such case following is the recurrence expression:-
T(n) = 2T(n/2) + Θ(n)
Thus time complexity for the above expression is Θ(nLogn).
2. Worst Case: This case is said to occur if the partitioning element is always with the smallest or greatest array element. In such case following is the recurrence:
T(n) = T(0) + T(n-1) + Θ(n)
which is equivalent to,
T(n) = T(n-1) + Θ(n)
Thus complexity in such a case is said to be Θ (n2).
3. Average Case: Such a case occurs when the partition occurs when partitioning divides the elements such that O(n/9) elements are in one set and 9n/10 in other. Recurrence in such case is,
T(n) = T(n/9) + T(9n/10) + Θ(n)
Time complexity is found to be Θ(nLogn).
The above algorithm needs some optimizations to reduce the complexity, such as taking pivot to be any random element or reciting the smaller array first and using the tail-recursive approach. Recursion requires a lot of space in the function call stack to store the left and right elements along with other parameters. Such a drawback can be avoided using the below iterative approach of QuickSort.
2. Iterative Version of Quick Sort
Here we will see the iterative version of quicksort.
Code:
def partition(myarr, left, right):
i = left - 1
x = myarr[right]
for j in range(left, right):
if myarr[j] <= x:
# increment index of smaleftlefter eleftement
i = i + 1
myarr[i], myarr[j] = myarr[j], myarr[i]
myarr[i + 1], myarr[right] = myarr[right], myarr[i + 1]
return (i + 1)
def qSortIterative(myarr, left, right):
size = right - left + 1
stack = [0] * (size)
top = -1
top = top + 1
stack[top] = left
top = top + 1
stack[top] = right
while top >= 0:
right = stack[top]
top = top - 1
left = stack[top]
top = top - 1
p = partition( myarr, left, right )
if p-1 > left:
top = top + 1
stack[top] = left
top = top + 1
stack[top] = p - 1
if p + 1 < right:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = right
myarr = [12,56,23,767,3,88,3,56,5]
n = len(myarr)
qSortIterative(myarr, 0, n-1)
print ("After Sorting myarray is")
for i in range(n):
print ("% d" % myarr[i]),
Output:
Code Explanation: Partition function is the same in both the programs. Only the call to Sort the element changes as here an auxiliary stack is used to store the elements and pop out and store them in a sorted manner. To reduce the size of the stack being used, one must push the smaller stack first.
Conclusion
Quick Sort method sorts the elements using the Divide and Conquer approach and has an average O(nLogn) complexity. It can be implemented in both recursive and iterative way. It is in-place, cache-friendly and also a tail-recursive algorithm. It is mostly preferred in case of arrays as a lot of access to elements is required, which consumes a lot of time in case of linked lists.
Recommended Articles
This is a guide to Quick Sort in Data Structure. Here we discuss the introduction and algorithm for quick sort in a data structure and code implementation. You can also go through our other suggested articles to learn more –
