Exercise_5.java

import java.util.*;

/*
 * 
 * Time Complexity : O(n^2) all are descending order
 * Space Complexity : O(n) ~ stack space
 * Did this code successfully run on Leetcode : No (Time limit exceeded)
 *  Any problem you faced while coding this : Swapping without extra variable, if we swap same index then result computes to 0. I didn't know and had to debug
 */

class IterativeQuickSort { 
    void swap(int arr[], int i, int j) 
    { 
	//Try swapping without extra variable 
        if(i != j) {
            arr[i] = arr[i] + arr[j];
            arr[j] = arr[i] - arr[j];
            arr[i] = arr[i] - arr[j];
        }
    } 
  
    /* This function is same in both iterative and 
       recursive*/
    int partition(int arr[], int l, int h) 
    { 
        //Compare elements and swap.
        int pivot = h;
        int j = l;
        int i = j - 1;

        while(j < pivot) {
            if(arr[j] < arr[pivot]) {
                i++;
                swap(arr, i, j);
                j++;
            } else {
                j++;
            }
        }

        i++;
        swap(arr, i, j);
        return i;
    } 
  
    // Sorts arr[l..h] using iterative QuickSort 
    void QuickSort(int arr[], int l, int h) 
    { 
        //Try using Stack Data Structure to remove recursion. 
        Stack<int[]> st = new Stack<>();
        st.add(new int[]{l,h});

        while(!st.isEmpty()) {
            int[] temp = st.pop();
            int low = temp[0];
            int high = temp[1];
            if(high > low) {
                int pivot = partition(arr, low, high);
                st.add(new int[]{low, pivot-1});
                st.add(new int[]{pivot+1, high});
            }
        }
    } 
  
    // A utility function to print contents of arr 
    void printArr(int arr[], int n) 
    { 
        int i; 
        for (i = 0; i < n; ++i) 
            System.out.print(arr[i] + " "); 
    } 
  
    // Driver code to test above 
    public static void main(String args[]) 
    { 
        IterativeQuickSort ob = new IterativeQuickSort(); 
        int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 }; 
        ob.QuickSort(arr, 0, arr.length - 1); 
        ob.printArr(arr, arr.length); 
    } 
}