PreCourse-2/Exercise_5.py at master · NickilVishwaaMS/PreCourse-2 · GitHub

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
#Time Complexity:O(nlog(n))
#Space COmplexity:O(nlog(n))
def partition(arr, l, h):
  pivot=arr[h]
  i=l -1
  j=l
  while(j<h):
    if arr[j]<=pivot:
        i=i+1
        (arr[i], arr[j]) = (arr[j], arr[i])
    j=j+1
  (arr[i + 1], arr[h]) = (arr[h], arr[i + 1])
  return i+1


def quickSortIterative(arr, l, h):
	size = h - l + 1
	stack = [0] * size
	top = -1
	top = top + 1
	stack[top] = l
	top = top + 1
	stack[top] = h
	while top >= 0:
		h = stack[top]
		top = top - 1
		l = stack[top]
		top = top - 1
		p = partition( arr, l, h )
		if p-1 > l:
			top = top + 1
			stack[top] = l
			top = top + 1
			stack[top] = p - 1
		if p+1 < h:
			top = top + 1
			stack[top] = p + 1
			top = top + 1
			stack[top] = h