01

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

### Data Structures & Algorithms For Beginners Free Course

## 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 best **Data Structures and Algorithms Course**, 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:

- Always pick the first element as a pivot.
- Always pick the last element as a pivot
- Pick a random element as a pivot.
- 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

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

- A
**pointer**is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index. - If the element is greater than the pivot element, a second pointer is set for that element.
- 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.
- Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another smaller element.
- The process goes on until the second last element is reached.
- Finally, the pivot element is swapped with the second pointer.

- A
- Divide Subarrays

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

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

**Time complexity****Case****Time Complexity****Best**O(nlogn) **Average**O(nlogn) **Worst**O(n^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

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

## Advantages of Quick Sort Algorithm

**Efficiency:**It is efficient on large data sets.**In-place sorting:**Quick sort performs**in-place sorting**, meaning it doesn't require additional memory to store temporary data or intermediate results.**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

**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.**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.**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.**Recursive Overhead:****Recursive function**calls consume additional memory and can lead to**stack overflow**errors when dealing with large data sets.**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.**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 **DSA Programming Course**.