Quick Sort – Data Structure and Algorithm

Serving as a pivotal sorting algorithm, much similar to the way a seasoned card player organizes their deck, quick sort employs a strategy that efficiently divides an array into manageable segments. Unlike insertion sort or selection sort, quick sort doesn’t hinge on individual element placements. Instead, it tackle a divide-and-conquer approach that pivots around the selection of a “pivot” element to partition the array into sections.

Quick sort Algorithm

In each iteration, quick sort selects a pivot element and rearranges the array such that all elements lesser than the pivot are placed on its left, and those greater are placed on the right. This “partitioning” process is the cornerstone of the algorithm’s efficiency. Subsequently, quick sort recurs on each of the partitioned segments, delving deeper into smaller chunks until the entire array is sorted.

Working of Quick sort Algorithm

For a comprehensive grasp of the concept, consider an example array: arr[] = {10, 90, 30, 80, 40, 50, 70}

110    90    30    80    40    50    70Initial array state
10    30    40    50    70    90    80After selecting 70 as the pivot and partitioning
210    30    40    50    70    90    80Sub-array [10, 30, 40, 50] sorted using recursion
310    30    40    50    70    80    90Sub-array [90, 80] sorted using recursion
410    30    40    50    70    80    90Entire array sorted
Recursion sorting involves dividing an array into smaller segments, sorting each segment through recursive calls, and then combining the sorted segments to achieve a fully sorted array. This technique leverages self-replicating function calls to efficiently manage sorting tasks.

Code in C++

This table explains each step of the Quick Sort algorithm implementation in C++ along with relevant code snippets.

1#include <iostream>Include necessary header files.
2#include <vector>Include the vector library for dynamic arrays.
3using namespace std;Use the standard namespace for convenience.
4int partition(vector<int>& arr, int low, int high) {…}Define the partition function to choose pivot and rearrange elements.
5    int pivot = arr[high];Choose the pivot element from the end.
6    int i = low – 1;Initialize the index of the smaller element.
7    for (int j = low; j < high; j++) {…}Iterate through the array to partition elements.
8        if (arr[j] < pivot) {…}If the current element is smaller than the pivot, swap it.
9            i++;Increment index of smaller element.
10            swap(arr[i], arr[j]);Swap elements to move smaller element to the left.
11    swap(arr[i + 1], arr[high]);Swap the pivot element to its correct position.
12    return i + 1;Return the index of the pivot element.
13void quickSort(vector<int>& arr, int low, int high) {…}Define the Quick Sort function.
14    if (low < high) {…}If the sub-array has more than one element.
15        int pivotIndex = partition(arr, low, high);Get the index of the pivot element after partitioning.
16        quickSort(arr, low, pivotIndex – 1);Recursively sort the left sub-array.
17        quickSort(arr, pivotIndex + 1, high);Recursively sort the right sub-array.
18int main() {…}Define the main function to test Quick Sort.
19    vector<int> arr = {…};Initialize an array for testing.
20    int n = arr.size();Get the size of the array.
21    quickSort(arr, 0, n – 1);Call Quick Sort function to sort the array.
22    cout << “Sorted array: “; {…}Print the sorted array as output.
23    return 0;Indicate successful program execution.

Complexity Analysis of Quick Sort

Time Complexity:

  • Worst-case time complexity: O(n^2)
  • Average-case time complexity: O(n log n)
  • Best-case time complexity: O(n log n)

Space Complexity:

In conclusion, quick sort stands as an efficient algorithm for sorting arrays. By strategically partitioning and sorting segments, it effectively builds up a fully sorted array. Its average-case time complexity outperforms other quadratic time algorithms, rendering it suitable for larger datasets. However, its worst-case scenario can still pose challenges, making it crucial to consider data characteristics before implementation. Understanding quick sort unveils its potential and contributes to a comprehensive understanding of sorting algorithms.

Merge Sort also used the Divide and Conquer technique for sorting.

Read more about Merge sort.

2 thoughts on “Quick Sort – Data Structure and Algorithm”

Leave a Comment