C++ Program For Iterative Quick Sort

In this tutorial, we will explore the C++ code for performing iterative quick sort. However, prior to delving into the implementation details, it is essential to understand the iterative quick sort along with its algorithm and a practical example.

One widely recognized sorting algorithm valued for its practical efficiency and effectiveness is known as 'Quick Sort'. While the recursive form of Quick Sort is commonly preferred, an alternative iterative approach can be developed to avoid the performance cost linked with recursive function invocations. This iterative technique relies on a stack to oversee the divisions of the array that require sorting.

The core concept behind Quick Sort involves partitioning the array elements into two sub-arrays based on their relation to a chosen pivot element. This pivot is selected from the array and the process is repeated recursively on the sub-arrays, ultimately sorting the entire array.

The partition method, responsible for selecting a pivot element and dividing the array, is established at the beginning of the program. The 'iterativeQuickSort' procedure employs a stack to manage the sub-arrays in need of sorting. Subsequently, it adds the divided sub-arrays back to the stack following the iterative removal and partitioning of sub-arrays using the partition method. This process iterates until the stack becomes empty, ensuring the proper sorting of every element.

The software utilizes a demonstration array to showcase its functionality. The array is displayed prior to and following the sorting process, illustrating the arrangement of elements in ascending order through the iterative Quick Sort algorithm.

Programmers can value the effectiveness of Quick Sort and enhance their understanding of optimizing sorting algorithms for real-world scenarios by grasping and implementing this iterative form of the algorithm. The utilization of an explicit stack in the iterative method sheds light on the trade-offs between recursion and iteration in designing algorithms.

Iterative Quicksort Algorithm

• ✅ Start
• ✅ Pick any element as a pivot.
• ✅ If the element is less than the pivot.
• ✅ Swap with the element at the index.
• ✅ Increment index.
• ✅ Push all the elements less than pivot to the left.
• ✅ Push all the elements greater elements to the right.
• ✅ Swap the rightmost element with the element at the index.
• ✅ Return index.
• ✅ Print sorted array.
• ✅ Stop

Complexity Analysis:

Time Complexity:

Quick Sort boasts an average and best-case time complexity of O(n log n), rendering it highly efficient for handling large datasets. Conversely, the time complexity can deteriorate to O(n^2) under the worst-case scenario when the pivot selection consistently leads to unbalanced partitions. Both the recursive and iterative implementations maintain identical time complexity characteristics.

Space Complexity:

Its memory needs do not increase in direct proportion to the input size, as Quick Sort operates as an in-place sorting technique. The non-recursive approach could potentially consume less memory compared to the recursive one, as it employs a specific stack for operations.

Example:

Let's consider a scenario to demonstrate the iterative implementation of quicksort in the C programming language:

#include <iostream>
#include <stack>
using namespace std;
//Function to partition the array and return the index of the pivot element
int partition(int arr[], int low, int high) 
{
 int pivot = arr[high];
 int i = low - 1;
 for (int j = low; j < high; ++j) 
 {
 if (arr[j] <= pivot)
 {
 ++i;
 swap(arr[i], arr[j]);
 }
 }
 swap(arr[i + 1], arr[high]);
 return i + 1;
}
//Function to perform iterative Quick Sort
void iterativeQuickSort(int arr[], int low, int high)
{
 stack<pair<int, int>> stk;
 stk.push({low, high});
 while (!stk.empty()) 
 {
 int start = stk.top().first;
 int end = stk.top().second;
 stk.pop();
 int pivotIndex = partition(arr, start, end);
 if (pivotIndex - 1 > start)
 {
 stk.push({start, pivotIndex - 1});
 }
 if (pivotIndex + 1 < end)
 {
 stk.push({pivotIndex + 1, end});
 }
 }
}
//Function to print the array
void printArray(int arr[], int size) 
{
 for (int i = 0; i < size; ++i)
 {
 cout << arr[i] << " ";
 }
 cout << endl;
}
int main()
{
 int arr[] = {12, 4, 5, 6, 7, 3, 1, 15};
 int size = sizeof(arr) / sizeof(arr[0]);
 cout << "Original array: ";
 printArray(arr, size);
 iterativeQuickSort(arr, 0, size - 1);
 cout << "Sorted array: ";
 printArray(arr, size);
 return 0;
}

Output:

Original array: 12 4 5 6 7 3 1 15 
Sorted array: 1 3 4 5 6 7 12 15

Explanation:

• ✅ In this example, the program includes the typical directives for C++. Include <iostream> header file to operate on input/output, and include <stack> to use the stack data structure .
• ✅ It is how the partition function works. Its parameters are the low index (low), the high index (high), and an array (arr). After selecting the pivot as the element at the high index, the Function rearranges the array's elements so that any element less than or equal to the pivot is on the left and any element more significant than the pivot is on the right. After dividing, the pivot element's index is returned.
• ✅ It is the Function known as iterativeQuickSort . The low index (low) , the high index (high), and an array (arr) are required. The sub-arrays that require sorting are tracked using a stack (stk). It uses a while loop to handle the sub-arrays iteratively. It removes a sub-array from the stack at the beginning of each iteration, divides it using the partition function, and pushes it back onto the stack if the sub-arrays are already sorted.
• ✅ After that, we use the printArray Function, whose parameters are an array (arr) and size (size). It outputs the array's elements to the standard output.
• ✅ The main function is the primary Function and the program's point of entry. First, an array is initialized, and then it uses the printArray Function to display the original array, the iterativeQuickSort method to sort it, and finally it displays the sorted array again.

Conclusion:

In summary, the software efficiently handles the sorting procedure by applying the iterative Quick Sort algorithm with the assistance of a stack. The task of rearranging elements with respect to a pivot is carried out by the partition method, while the iterativeQuickSort Function executes the sorting process in an iterative manner with the support of a stack. By demonstrating with a sample array, the main Function illustrates the application of these methods.