# Quick Sort Algorithm in Data Structures - Its Types ( With Examples )

06 Jun 2024
Intermediate
10K Views
Learn via Video Course & by Doing Hands-on Labs

## Quick Sort: An Overview

We saw that the Merge Sort Algorithm works according to the Divide and Conquer principle. In this DSA tutorial, we are going to learn one more algorithm that works on the same principle but in a little different manner. To further enhance your understanding and application of quick-sort concepts, consider enrolling in the Dsa Training, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

## What is Quick Sort in Data Structures?

Quick sort is a highly efficient, comparison-based sorting algorithm that follows the divide-and-conquer strategy. It works by selecting a pivot element from the array and partitioning the array into two sub-arrays around that pivot. One subarray contains elements smaller than the pivot element, and the other subarray contains elements greater than the pivot element. The left and right subarrays are also divided using the same approach. This process continues recursively until each subarray contains a single element. All these subarrays are then combined to form a single sorted array.

### How to select the pivot element?

There are many different ways of selecting pivots:

1. Always pick the first element as a pivot.
2. Always pick the last element as a pivot
3. Pick a random element as a pivot.
4. Pick the middle element as the pivot.

## Quick Sort Algorithm

``````quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)

partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
``````

### Working of Quick Sort Algorithm

1. Pivot Selection: Choose a pivot element from the array at your convenience. For the sake of simplicity, let's assume the last element is the pivot.

2. Partitioning: Rearrange the array such that all elements less than the pivot are placed before it, and all elements greater than the pivot are placed after it.

Here's how we rearrange the array:

1. A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index.

2. If the element is greater than the pivot element, a second pointer is set for that element.

3. Now, pivot is compared with other elements. If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.

4. Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another smaller element.

5. The process goes on until the second last element is reached.

6. Finally, the pivot element is swapped with the second pointer.
3. Divide Subarrays

The subarrays are divided until each subarray is formed of a single element. At this point, the array is already sorted.

Read More - Data Structure Interview Questions for Freshers

## Implementation of Quick Sort in Different Languages in Data Structures

``````
# Function to find the partition position
def partition(array, low, high):
# Choose the rightmost element as pivot
pivot = array[high]
# Pointer for greater element
i = low - 1

# Traverse through all elements
# Compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# Swap it with the greater element pointed by i
i = i + 1
# Swapping element at i with element at j
array[i], array[j] = array[j], array[i]

# Swap the pivot element with the greater element specified by i
array[i + 1], array[high] = array[high], array[i + 1]

# Return the position from where partition is done
return i + 1

# Function to perform quicksort
def quickSort(array, low, high):
if low < high:
# Find pivot element such that
# Elements smaller than pivot are on the left
# Elements greater than pivot are on the right
pi = partition(array, low, high)

# Recursive call on the left of pivot
quickSort(array, low, pi - 1)
# Recursive call on the right of pivot
quickSort(array, pi + 1, high)

def print_list(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()

arr = [7, 2, 1, 6, 8, 5, 3, 4]
print("Original array is:", end=" ")
print_list(arr)

size = len(arr)
quickSort(arr, 0, size - 1)

print('Sorted Array in Ascending Order:', end=" ")
print_list(arr)
``````
``````
public class QuickSort {

// Function to find the partition position
static int partition(int[] array, int low, int high) {
// Choose the rightmost element as pivot
int pivot = array[high];
// Pointer for greater element
int i = low - 1;

// Traverse through all elements
// Compare each element with pivot
for (int j = low; j < high; ++j) {
if (array[j] <= pivot) {
// If element smaller than pivot is found
// Swap it with the greater element pointed by i
i = i + 1;
// Swapping element at i with element at j
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

// Swap the pivot element with the greater element specified by i
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;

// Return the position from where partition is done
return i + 1;
}

// Function to perform quicksort
static void quickSort(int[] array, int low, int high) {
if (low < high) {
// Find pivot element such that
// Elements smaller than pivot are on the left
// Elements greater than pivot are on the right
int pi = partition(array, low, high);

// Recursive call on the left of pivot
quickSort(array, low, pi - 1);
// Recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}

public static void main(String[] args) {
int[] arr = {7, 2, 1, 6, 8, 5, 3, 4};
System.out.print("Original array is: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();

int size = arr.length;
quickSort(arr, 0, size - 1);

System.out.print("Sorted Array in Ascending Order: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
``````
``````

#include <iostream>
using namespace std;

// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}

// function to print the array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}

// function to rearrange array (find the partition point)
int partition(int array[], int low, int high) {

// select the rightmost element as pivot
int pivot = array[high];

// pointer for greater element
int i = (low - 1);

// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {

// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;

// swap element at i with element at j
swap(&array[i], &array[j]);
}
}

// swap pivot with the greater element at i
swap(&array[i + 1], &array[high]);

// return the partition point
return (i + 1);
}

void quickSort(int array[], int low, int high) {
if (low < high) {

// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on righ of pivot
int pi = partition(array, low, high);

// recursive call on the left of pivot
quickSort(array, low, pi - 1);

// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}

// Driver code
int main() {
int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original array is: ";
printArray(arr, n);

// perform quicksort on data
quickSort(arr, 0, n - 1);

cout << "Sorted Array in Ascending Order: ";
printArray(arr, n);
}
``````

#### Output

``````Original array is: 7 2 1 6 8 5 3 4
Sorted Array in Ascending Order: 1 2 3 4 5 6 7 8
``````

## Complexity Analysis of Quick Sort Algorithm

1. Time complexity
 Case Time Complexity Best O(nlogn) Average O(nlogn) Worst O(n^2)
2. Space complexity: In the worst case, the space complexity is O(n) because here, n recursive calls are made. And, the average space complexity of a quick sort algorithm is equal to O(logn).

## Applications of Quick Sort Algorithm

1. Numerical analysis:For accuracy in calculations most of the efficiently developed algorithm uses a priority queue and quick sort is used for sorting.
2. Call Optimization: It is tail-recursive and hence all the call optimization can be done.
3. Database management: Quicksort is the fastest algorithm so it is widely used as a better way of searching.

## Advantages of Quick Sort Algorithm

1. Efficiency: It is efficient on large data sets.
2. In-place sorting: Quick sort performs in-place sorting, meaning it doesn't require additional memory to store temporary data or intermediate results.
3. Simple implementation: Quick sort's algorithmic logic is relatively straightforward, making it easier to understand and implement compared to some other complex sorting algorithms

## Disadvantages of Quick Sort Algorithm

1. Unstable Sorting: Quick sort is an unstable sorting algorithm, meaning that it does not guarantee the relative order of equal elements after the sorting process.
2. Worst-case Performance: Its worst-case time complexity is O(n^2). It occurs when the pivot chosen is the smallest or largest element in the array, causing unbalanced partitions.
3. Dependency on Pivot Selection: The choice of pivot significantly affects the performance of quick sort. This issue is particularly prominent when dealing with already sorted or nearly sorted arrays.
4. Recursive Overhead: Recursive function calls consume additional memory and can lead to stack overflow errors when dealing with large data sets.
5. Not Adaptive: Quick sort does not take advantage of any pre-existing order or partially sorted input. This means that even if a portion of the array is already sorted, the quick sort will still perform partitioning operations on the entire array.
6. Inefficient for Small Data Sets: Quick sort has additional overhead in comparison to some simpler sorting algorithms, especially when dealing with small data sets. The recursive nature of quick sort and the constant splitting of the array can be inefficient for sorting small arrays.
##### Summary

So, here we saw every aspect of the quick sort algorithm in data structures. It must not have been difficult to understand if you understood Merge Sort in Data Structures properly. To apply your knowledge of merge sort algorithm, enroll in our Data Structures Certification.

## FAQs

### Q1. Which is better — merge sort or quick sort?

Quicksort is an in-space sorting algorithm as it doesn’t require any additional space to sort the given array. On the other hand, merge sort requires an auxiliary array to merge the sorted sublists. Hence, we can say that the quicksort has an advantage over the merge sort in terms of space.

### Q2. Is Quick Sort stable?

The default implementation is not stable. However, any sorting algorithm can be made stable by considering indices as a comparison parameter.

### Q3. How to pick any element as a pivot?

With one minor change to the above code, we can pick any element as a pivot. For example, to make the first element a pivot, we can simply swap the first and last elements and then use the same code. The same thing can be done to pick any random element as a pivot.

### Q4. Can we implement Quick Sort Iteratively?

Yes, it can be done.
Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 Angular Certification Course Jun 16 SAT, SUN Filling Fast 09:30AM to 11:30AM (IST) Advanced Full-Stack .NET Developer Certification Training Jun 17 MON, WED, FRI Filling Fast 07:00AM to 08:30AM (IST) ASP.NET Core Certification Training Jun 17 MON, WED, FRI Filling Fast 07:00AM to 08:30AM (IST) .NET Microservices Certification Training Jun 23 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) ASP.NET Core (Project) Jun 23 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Azure Developer Certification Training Jun 23 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) React JS Certification Training | Best React Training Course Jun 30 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) ASP.NET Core Certification Training Jun 30 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Advanced Full-Stack .NET Developer Certification Training Jun 30 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Generative AI For Software Developers Jul 14 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST)

Can't find convenient schedule? Let us know

Similar Articles