CS142_2020/quickSort.py at master · Abhijit-niser/CS142_2020 · 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Quick Sort
'''
- i
6,7,4,8,2,
- - j

- - i
6 4 7 8 2
- - - j

- - - i
6 4 2 8 7
- - - - - j
    p
2 4 6 8 7


i = pivot + 1 (will control the length of the short list)
j = pivot + 1 (move through the list)
6
'''

def partition(iL, low , high):
    # choose pivot
    pivot = iL[low]
    # declare i
    i = low + 1
    # loop n-1 times (j)
    for j in range(low+1,high):
        # Compare j with pivot
        # if j < pivot
        if iL[j] < pivot:
            # swap j with i
            iL[i], iL[j] = iL[j], iL[i]
            # increase i by 1
            i = i + 1
    # swap pivot
    iL[low], iL[i-1] = iL[i-1] , iL[low]
    # return pivot position
    return (i-1)

def quickSort(iL, low , high):
    if low < high:
        # Get pivot position from partition
        pp = partition(iL, low, high)
        # Quicksort on left
        # print("Calling quickSort on left")
        quickSort(iL, low , pp)
        # quicksort on right
        # print("Calling quickSort on right")
        quickSort(iL, pp + 1 , high)

a = [6,5,4,3,2,1]
quickSort(a, 0, len(a))
print(a)