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

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.

Similar Sorting Algorithms

• Insertion Sort
• Merge Sort
• Selection Sort
• Bucket Sort