Two ways of create a quicksort algorithm by Python

 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

# change the position on each number
def swapEachOther(arr, leftIndex, rightIndex):
    tmp = arr[leftIndex]
    arr[leftIndex] = arr[rightIndex]
    arr[rightIndex] = tmp
    print(arr)

# quck sort method : start from first number by pivot
def sort(arr, startIndex, endIndex):
    if startIndex >= endIndex:
        return

    leftIndex = startIndex
    rightIndex = endIndex

    # set the first pivot by first number
    compareValue = arr[startIndex]

    while leftIndex < rightIndex:
        # find the next pivot that was smaller than compareValue from right
        while leftIndex < rightIndex and arr[rightIndex] > compareValue:
            rightIndex = rightIndex - 1
        
        # find the next pivot that was bigger than compareValue from left
        while leftIndex < rightIndex and arr[leftIndex] <= compareValue:
            leftIndex = leftIndex + 1

        # while finding the next pivot, move smaller number to left and move bigger number to right
        if leftIndex < rightIndex:
            swapEachOther(arr, leftIndex, rightIndex)

    # move the pivot to the middle posotion
    swapEachOther(arr, startIndex, rightIndex)
    # use the sort method on left half array
    sort(arr, startIndex, rightIndex - 1)
    # use the sort method on right half array
    sort(arr, rightIndex + 1, endIndex)


arr = [3, 1, 2, 9, 4, 10, 5, 8, 6, 7]
print(arr)
sort(arr, 0, len(arr) -1)

 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

# change the position on each number
def swapEachOther(arr, leftIndex, rightIndex):
    tmp = arr[leftIndex]
    arr[leftIndex] = arr[rightIndex]
    arr[rightIndex] = tmp
    print(arr)

# quck sort method : 
def sort(arr, startIndex, endIndex):
    if startIndex >= endIndex:
        return

    # set the last number as the pivot number
    pivotIndex = endIndex

    # set the partitionIndex before the startIndex
    partitionIndex = startIndex -1

    # change the positon when it smaller than pivot number from left
    for i in  range(startIndex, endIndex):
        if arr[i] <= arr[pivotIndex]:
            # move the smaller number to the left of bigger number than pivot
            partitionIndex = partitionIndex + 1
            swapEachOther(arr, partitionIndex, i)
    
    # get the partitionIndex that will be cut the array in half
    partitionIndex = partitionIndex + 1

    # move the pivot to the middle posotion
    swapEachOther(arr, partitionIndex, pivotIndex)
    
    # use the sort method on left half array
    sort(arr, startIndex, partitionIndex - 1)
    # use the sort method on right half array
    sort(arr, partitionIndex + 1, endIndex)

arr = [3, 1, 2, 9, 4, 10, 5, 8, 6, 7]
print(arr)
sort(arr, 0, len(arr) -1)