-
Notifications
You must be signed in to change notification settings - Fork 0
/
Quick_Sort.py
60 lines (51 loc) · 1.9 KB
/
Quick_Sort.py
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
"""
Quick Sort is a Divide and Conquer algorithm.
It picks an element as a pivot and partitions the given array around the picked pivot.
Given an array arr[], its starting position is low (the index of the array) and
its ending position is high(the index of the array).
Consider the last element as the pivot such that all the elements less than(or equal to) the pivot lie before it
and the elements greater than it lie after the pivot.
Note: The low and high are inclusive.
Example: Input: N = 5, arr[] = { 4, 1, 3, 9, 7}
Output: 1 3 4 7 9
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(logN)
Constraints:
1 <= N <= 103
1 <= arr[i] <= 104
"""
# with Lomuto partition - (takes pivot high as expected in the practice)
class Solution:
def quickSort(self, arr, low, high):
if low < high:
pivotPos = self.partition(arr, low, high)
self.quickSort(arr, low, pivotPos - 1)
self.quickSort(arr, pivotPos + 1, high)
def partition(self, arr, low, high):
pivot = arr[high]
pos = low - 1
for id in range(low, high):
if arr[id] <= pivot:
pos += 1
arr[pos], arr[id] = arr[id], arr[pos]
arr[pos + 1], arr[high] = arr[high], arr[pos + 1]
return pos + 1
# with Hoare's partition (pivot is taken as low to exercise)
class Solution:
def quickSort(self, arr, low, high):
if low < high:
pivotPos = self.partition(arr, low, high)
self.quickSort(arr, low, pivotPos - 1)
self.quickSort(arr, pivotPos + 1, high)
def partition(self, arr, low, high):
pivot = arr[low]
i = low
j = high
while (True):
while (arr[i] < pivot):
i += 1
while (arr[j] > pivot):
j -= 1
if (i >= j):
return j
arr[i], arr[j] = arr[j], arr[i]