Repository navigation
Expand file tree
/
Copy pathExercise_5.java
More file actions
71 lines (61 loc) · 1.58 KB
/
Copy pathExercise_5.java
File metadata and controls
71 lines (61 loc) · 1.58 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Stack;
class IterativeQuickSort {
void swap(int arr[], int i, int j)
{
//Try swapping without extra variable
if(i==j)return;
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=arr[h];
int j=l;
for(int i=l;i<h;i++){
if(arr[i]<pivot){
swap(arr,i,j);
j++;
}
}
swap(arr,h,j);
return j;
}
// 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[]> stk=new Stack<>();
stk.push(new int[]{l,h});
while(!stk.isEmpty()){
int[] array=stk.pop();
int left=array[0];
int right=array[1];
int pos=partition(arr,left,right);
if(pos>left){
stk.push(new int[]{left,pos-1});
}
if(pos<right){
stk.push(new int[]{pos+1,right});
}
}
}
// 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);
}
}