Quick Sort is an efficient, inplace, and widelyused sorting algorithm that follows the divideandconquer paradigm. The key idea behind Quick Sort is to select a “pivot” element from the array and partition the other elements into two subarrays according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted. Quick Sort is known for its averagecase time complexity of O(n log n) and its ability to sort inplace without requiring additional memory.
Quick Sort works by recursively partitioning the array and sorting the partitions. Here’s a breakdown of the core components of Quick Sort:

Partitioning:
 The partition function is at the heart of Quick Sort. It selects a pivot element (in this implementation, the last element of the array) and rearranges the array such that all elements less than the pivot are moved to its left, and all elements greater than the pivot are moved to its right.
 The function then returns the index of the pivot element, which is now in its correct position in the sorted array.

Recursive Sorting:
 After partitioning, the Quick Sort function is called recursively on the subarrays to the left and right of the pivot. These recursive calls continue until the base case is reached (i.e., when the subarray has one or no elements, which is inherently sorted).

Swapping:
 The
swap
function is used within the partitioning process to exchange elements in the array. This helps in placing elements smaller than the pivot to its left and larger ones to its right.
 The
Code Explanation
// Function to swap elements
void swap(vector<int>& arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Partition function
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // Pivot is the last element
int i = low  1; // Index of the smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // If current element is smaller than the pivot
i++;
swap(arr, i, j); // Swap it with the element at i
}
}
swap(arr, i + 1, high); // Place the pivot in the correct position
return i + 1; // Return the partition index
}
// Quick sort function
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partition the array
quickSort(arr, low, pi  1); // Recursively sort the left subarray
quickSort(arr, pi + 1, high); // Recursively sort the right subarray
}
}
How It Works

Pivot Selection: The last element of the array segment is chosen as the pivot. While other pivot selection strategies exist, such as choosing the first element, middle element, or even a random element, the choice of pivot can significantly affect the performance of Quick Sort.

Partitioning Process: The array is partitioned around the pivot:
 Elements less than the pivot are moved to the left of the pivot.
 Elements greater than the pivot are moved to the right.
 The pivot is then placed in its correct sorted position.

Recursion: The array is recursively divided into subarrays and sorted. The base case for the recursion is when the subarray has only one or no elements, at which point no further sorting is necessary.
Complexity Analysis

Time Complexity:
 Average Case: O(n log n), where
n
is the number of elements in the array. This occurs when the pivot divides the array into two roughly equal halves.  Worst Case: O(n^2), which can occur if the pivot chosen is the smallest or largest element repeatedly, resulting in highly unbalanced partitions. This is mitigated in practice by choosing better pivot selection strategies (e.g., random pivot).
 Average Case: O(n log n), where

Space Complexity: O(log n) for the recursive stack space. Quick Sort is an inplace sorting algorithm, meaning it requires only a small amount of extra memory space for recursion, making it memory efficient.