Quick sort and quick select

Posted on | In

Quick sort and quick selection are algorithms based on the partition algorithm. Partition algorithm makes a two sublist($\mathcal{A},\mathcal{B}$) and one value(pivot$ = \gamma$). Every element in $\mathcal{A}$ is less or equal than $\gamma$. Every element in $\mathcal{B}$ is greater than $\gamma$. Notice that $\mathcal{A}$ can have some elements which have the same value with $\gamma$ but not $\gamma$ itself and $\mathcal{A},\mathcal{B}$ may be $\emptyset$. As a result, partition function makes $\gamma$ is the highest value of $\mathcal{A}$. Quick sort uses this property to sort the list. After partition function, $\mathcal{A}$ and $\mathcal{B}$ is sorted to each other by $\gamma$. Therefore, quick sort just sort recursively in $\mathcal{A}$ and $\mathcal{B}$. Quick selection do the simillar thing. Quick selection is an algorithm to find a $n$th element in the entire list. If the order of $\gamma$ is equal with what you seek for, it’s done. If the order of $\gamma$ is less than what you seek for, adjust the order to find and try to check $\gamma$ in $\mathcal{B}$ again. If the order of $\gamma$ is greater than what you seek for, adjust the order to find and try to check $\gamma$ in $\mathcal{A}$ again. It works like semi-quick sort, it sorts a little bit and tries to find the elements in $n$th order and keep going on.

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def partition(lst, fromIdx, toIdx):
    '''
    Q-sort partition algorithm
    [fromIdx,   toIdx)
    inclusive, exclusive

    It is inplace, mutatable function
    return list partition point of pivot
    (smaller or equal than pivot) (pivot) (larger than pivot)
    '''
    selectPoint = int((toIdx + fromIdx)/2)
    lst[fromIdx],lst[selectPoint] = lst[selectPoint],lst[fromIdx]
    criteria = lst[fromIdx]
    lIdx = fromIdx
    rIdx = toIdx - 1
    while lIdx < rIdx:
        while lIdx < rIdx:
            if lst[lIdx] > criteria:
                break
            lIdx += 1
        if lIdx == rIdx:
            break
        while lIdx < rIdx:
            if lst[rIdx] <= criteria:
                break
            rIdx -= 1
        lst[lIdx], lst[rIdx] = lst[rIdx], lst[lIdx]
    if lst[lIdx] > lst[fromIdx]:
        lIdx -= 1
    lst[lIdx], lst[fromIdx] = lst[fromIdx], lst[lIdx]
    return lIdx

def _qsort(lst, fromIdx, toIdx):
    if toIdx - fromIdx <= 1:
        return
    mid = partition(lst, fromIdx, toIdx)
    _qsort(lst, fromIdx, mid)
    _qsort(lst, mid + 1, toIdx)
    
def qsort(lst):
    _qsort(lst, 0, len(lst))

def _qselect(lst, idx, fromIdx, toIdx):
    if toIdx - fromIdx <= 1:
        return
    mid = partition(lst, fromIdx, toIdx)
    if mid == idx:
        return
    if idx < mid: # target is inside of left handSide
        _qselect(lst, idx, fromIdx, mid)
    else:
        _qselect(lst, idx, mid + 1, toIdx)
    
    
def qselect(lst, idx):
    if len(lst) <= idx:
        return -1
    _qselect(lst, idx, 0, len(lst))
    return lst[idx]

#Test code
import random

if __name__ == "__main__":
    for i in range(1000):
        lst = []
        for j in range(1000):
            lst.append(random.randint(0,100))
        targetIdx = random.randint(0,len(lst) - 1)
        lst2 = list(lst)

        #Highly crush the qsort
        #lst2[0] = 0

        qsort(lst2)
        if sorted(lst) != lst2:
            print('wrong result for qsort')
            raise
        
        #Lowly crush the qselect
        #lst[0] = lst[0] - 1
        #Highly crush the qselect
        #lst[0] = lst[0] - 20
        if qselect(lst, targetIdx) != lst2[targetIdx]:
            print('wrong result for qselect')
            raise
    print('Every thing done well!')