QuickSort Working

Partition Process

In quicksort, the key process is partition, which sorts the array such that all the elements to the left of the pivot are smaller than or equal to the pivot and all the elements to the right of the pivot are greater than the pivot in case of increasing order. This function has the time complexity of O(n) and space complexity of O(1). This function returns the sorted position of the pivot in the array....

QuickSort Working

The quicksort works by repeatedly dividing the array into two subarrays around the pivot position returned by the partition funciton. The working of the quicksort algorithm is:...

Algorithm for the Iterative Quicksort

After understanding the quicksort, we will see how we can implement quicksort using loops:...

C++ Program for Iterative QuickSort

C++ // C++ program to implement the iterative quicksort #include using namespace std;    // Function to swap two elements void swap(int* a, int* b) {     int t = *a;     *a = *b;     *b = t; }    // partition process int partition(int arr[], int first, int last) {     int pivot = arr[last];        int i = first;     for (int j = first; j < last; j++) {         if (arr[j] <= pivot) {             swap(&arr[i], &arr[j]);             i++;         }     }     swap(&arr[i], &arr[last]);     return (i); }    // iterative quick sort void quickSortIterative(int arr[], int first, int last) {     int stack[last - first + 1];     int top = -1;     stack[++top] = first;     stack[++top] = last;     while (top >= 0) {         last = stack[top--];         first = stack[top--];         int pivot_pos = partition(arr, first, last);            // If there are elements on left side of pivot, then         // push left side to stack         if (pivot_pos - 1 > first) {             stack[++top] = first;             stack[++top] = pivot_pos - 1;         }            // If there are elements on right side of pivot,         // then push right side to stack         if (pivot_pos + 1 < last) {             stack[++top] = pivot_pos + 1;             stack[++top] = last;         }     } }    // driver code int main() {     int size = 10;     int arr[size] = { 10, 23, 4, 0, 8, 5, 9, 11, 22, 3 };        quickSortIterative(arr, 0, size - 1);        cout << "Elements after sorting:";     for (int i = 0; i < size; i++) {         cout << arr[i] << " ";     }        return 0; };...